骑士之战

时间限制: 1 Sec  内存限制: 128 MB

题目描述

有n位骑士想要通过淘汰赛决出他们当中最强大的一个。所有的骑士由1到n编号，他们总共进行了m场比赛，在第i场比赛中，所有编号在li到ri之间且尚未出局的骑士进行了一场比赛，决出了获胜者xi，其他参加比赛的骑士就出局了；我们称这些骑士被骑士xi打败了。m场比赛过后，只有一位骑士还没有出局，他就是最终的获胜者，我们希望知道其他所有骑士分别是被谁打败了。

 

输入

第一行包含两个正整数n和m，表示骑士和比赛的数量。
接下来m行，每行三个数l，r和x，表示参与比赛的骑士编号范围，以及获胜者的编号。

 

 

输出

输出n个由空格分隔的整数，第i个表示打败骑士i的骑士的编号。如果骑士i是获胜者，就在对应位置输出0。

 

样例输入

复制样例数据

5 3
2 4 3
1 3 1
1 5 5

样例输出

5 3 1 3 0

提示

第一场比赛中，骑士3打败了骑士2和4。 第二场比赛中，骑士1打败了骑士3。 第三场比赛中，骑士5打败了骑士1。 最终的胜利者是骑士5。

对于30%的数据，n ≤ 1000；
对于100%的数据，1 ≤ m < n ≤ 3×106, 1 ≤ l ≤ x ≤ r ≤ n,保证l到r之间至少有两位尚未出局的骑士，且骑士x一定尚未出局。

用指针复杂度为O(n);

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int ans[3000005];

struct node
{
	int l, r;
}a[3000005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d",&n, &m);
	for (int i = 1; i <= n; i++) a[i].l = i - 1, a[i].r = i + 1;
	int l, r, x;
	for (int i = 1; i <= m; i++){
		scanf("%d %d %d", &l, &r, &x);
		int cnt = a[x].l;
		while(cnt >= l){
			ans[cnt] = x;
			a[a[cnt].l].r = a[cnt].r;
			a[a[cnt].r].l = a[cnt].l;
			cnt = a[cnt].l;
		}
		cnt = a[x].r;
		while(cnt <= r){
			ans[cnt] = x;
			a[a[cnt].l].r = a[cnt].r;
			a[a[cnt].r].l = a[cnt].l;
			cnt = a[cnt].r;
		}
	}
	printf("%d", ans[1]);
	for (int i = 2; i <= n; i++) printf(" %d", ans[i]);
	printf("\n");

	return 0;
}
/**/