SPOJ-CLFLARR 题解

把操作倒着做，每次操作只需要考虑没有颜色的点即可
维护(f[i])为[i,n]中最前面的没有颜色的点的编号。只需要疯狂从(find(l))向后跳为止，同时修改(f[i]=i+1)
复杂度均摊一下，每个点最多被操控一次，所以复杂度是(Theta(nlogn))的。

#include <bits/stdc++.h>
#define dbg(x) std::cerr << #x << " = " << x << "
"
using namespace std;
typedef long long ll;

const int N = 200000 + 10;
int n, q, f[N], l[N], r[N], c[N], color[N];
int find(int x) {
	return x == f[x] ? f[x] : f[x] = find(f[x]);
}
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n + 1; i++) f[i] = i;
	for(int i = 1; i <= q; i++) scanf("%d%d%d", &l[i], &r[i], &c[i]);
	for(int i = q; i >= 1; i--) {
		for(int j = find(l[i]); j <= r[i]; j = find(j)) {
			color[j] = c[i];
			f[j] = j + 1;
		}
	}
	
	for(int i = 1; i <= n; i++) printf("%d
", color[i]);
	return 0;
}