染色

题目描述

在一条数轴上有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(n²))超时了。

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

可以维护每个点右边最近的黑点的位 置   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;
}