题解 P1840 【Color the Axis_NOI导刊2011提高（05）】
凌幽
2017-10-25 17:32:32
看了看各位大佬的题解,都是线段树,那我就来一份并查集的题解吧
给一段区间染色,可以看做是合并一段区间,并且使其在统计过程中不会重复统计
固定染色区间的左端点,将整个区间合并(从右向左扫一边染色区间),这样当我们统计区间时用x=find(x)时就相当于跳过该区间,达到了不重复的目的
部分代码
```cpp
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);
}
```