题目描述
在一条数轴上有n个点，分别为1-n 。一开始所有的点都被染成黑色。接着进行m次操作，第i次操作将[l,r]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。
输入格式
输入第一行为n和 m。
下面一行每行两个数l,r 。
输出格式
输出m行，为每次操作后剩余黑色点的个数。
样例
样例输入
10 3
3 3
5 7
2 8
样例输出
9
6
3
分析
将[l,r]区间内的黑点染成白点。最朴素的方法是，从l到r逐个排查每个点，将黑点变白，统计黑点个数。时间复杂度(O(n2))超时了。
本题关键是提高查找区间内黑点位置的效率。
可以维护每个点右边最近的黑点的位 置 fa[p]
这样查找p向右最近的黑点位置时候可以跳过白点，p=fa[p]。
为了跳得更快点，可以路径压缩 :p=find(p) (并查集中的“查”)
染色操作的影响：
将p点染色后 ，p向右最近的黑点位置就是p+1点向右最近的黑点位置fa[p]=find[p+1](并查集中的“并”)
代码参考
#include <bits/stdc++.h>
using namespace std;
#define re register
#define LL long long
inline int read() {
int f = 1, lzx = 0;
char c = getchar();
while ((c > '9') || (c < '0')) {
if (c == '-')
f = -f;
c = getchar();
}
while (c <= '9' && c >= '0') {
lzx = lzx * 10 + c - '0';
c = getchar();
}
return lzx * f;
}
const int MAXN = 1e6 + 10;
int n, m, l, r, fa[MAXN];
inline int find(int x) {
if (fa[x] == 0)
return x;
return fa[x] = find(fa[x]);
}
int main() {
n = read();
m = read();
int s = n;
for (int i = 1; i <= m; i++) {
l = read();
r = read();
for (;;) {
l = find(l);
if (l > r)
break;
// 染白l位置的点
s--; // 黑点个数减1
fa[l] = find(l + 1); // l右边最近的黑点位置，就是l+1右边最近的黑点位置.
}
printf("%d\n", s);
}
return 0;
}