染色

flatte / 2023-07-30 / 原文

在一条数轴上有n个点，分别为1-n 。一开始所有的点都被染成黑色。接着进行m次操作，第i次操作将[l,r]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。

输入第一行为n和 m。

下面一行每行两个数l,r 。

输出m行，为每次操作后剩余黑色点的个数。

样例输入

样例输出

9
6
3

分析

将[l,r]区间内的黑点染成白点。最朴素的方法是，从l到r逐个排查每个点，将黑点变白，统计黑点个数。时间复杂度(O(n²))超时了。

本题关键是提高查找区间内黑点位置的效率。

可以维护每个点右边最近的黑点的位置 fa[p]

这样查找p向右最近的黑点位置时候可以跳过白点，p=fa[p]。

为了跳得更快点，可以路径压缩 :p=find(p) (并查集中的“查”)

染色操作的影响：

将p点染色后，p向右最近的黑点位置就是p+1点向右最近的黑点位置fa[p]=p+1(并查集中的“并”)

代码参考

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define re register
 4 
 5 #define LL long long
 6 
 7 inline int read() {
 8     int f = 1, lzx = 0;
 9     char c = getchar();
10     while ((c > '9') || (c < '0')) {
11         if (c == '-')
12             f = -f;
13         c = getchar();
14     }
15     while (c <= '9' && c >= '0') {
16         lzx = lzx * 10 + c - '0';
17         c = getchar();
18     }
19     return lzx * f;
20 }
21 const int MAXN = 1e6 + 10;
22 int n, m, l, r, fa[MAXN];
23 inline int find(int x) {
24     if (fa[x] == 0)
25         return x;
26     return fa[x] = find(fa[x]);
27 }
28 
29 int main() {
30     n = read();
31     m = read();
32     int s = n;
33     for (int i = 1; i <= m; i++) {
34         l = read();
35         r = read();
36         for (;;) {
37             l = find(l);
38             if (l > r)
39                 break;
40             // 染白l位置的点
41             s--;                  // 黑点个数减1
42             fa[l] = find(l + 1);  // l右边最近的黑点位置,等于l+1右边最近的位置。
43         }
44         printf("%d\n", s);
45     }
46 
47     return 0;
48 }