自动搬运

查看原文

来自洛谷，原作者为

	凌幽 愿君得偿所愿（顺便凌幽是无忧的同音诶

搬运于2025-08-24 21:30:56，当前版本为作者最后更新于2017-10-25 17:32:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了看各位大佬的题解,都是线段树,那我就来一份并查集的题解吧

给一段区间染色,可以看做是合并一段区间,并且使其在统计过程中不会重复统计

固定染色区间的左端点,将整个区间合并(从右向左扫一边染色区间),这样当我们统计区间时用x=find(x)时就相当于跳过该区间,达到了不重复的目的

部分代码

int n,m;
int cnt;
int fa[200005];
inline int found(int x){
    return x==fa[x]?x:fa[x]=found(fa[x]);
}
inline int dy(){
    in(n),in(m);
    for(R int i=0;i<=n+1;++i)fa[i]=i;
    while(m--){
        R int a,b;in(a),in(b);
        b=found(b);
        while(a<=b){
            if(a!=b && found(a)==b)break;
            fa[b]=found(fa[b-1]);
            cnt++;
            b=found(b);
        }
        write(n-cnt),putchar('\n');        
    }
    exit(0);
}