并查集小妙用
把操作倒着做，每次操作只需要考虑没有颜色的点即可
维护$f[i]$为[i,n]中最前面的没有颜色的点的编号。只需要疯狂从$find(l)$向后跳为止，同时修改$f[i]=i+1$
复杂度均摊一下，每个点最多被操控一次，所以复杂度是$\Theta(nlogn)$的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
#define dbg(x) std::cerr << #x << " = " << x << "\n"
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\n", color[i]);
return 0;
}
|
另附一些并查集小妙用：
RMQ:离线，将$[l,r]$push进一个以r为下标的vector里。依次加入每个数，维护$f[i]$为在i后面第一个比i小的数的下标，显然可以贪心的跳$f$找到最小值。
$f$可以单调栈维护。对于每个$l$，答案就是目前的$a[find(l)]$.