题解 P1840 【Color the Axis_NOI导刊2011提高（05）】

凌幽 · 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);
}