并查集的区间染色
并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。
在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。
以例题来做具体解释。
[CF356A Knight Toumament](Problem - A - Codeforces)
题意
\(n\) 个骑士编号从 \(1\) 到 \(n\)，给出 \(m\) 场决斗。每场决斗给出 \(l , r, x\) 表示区间 \([l,r]\) 之间还没被打败的骑士之间进行决斗，编号为 \(x\) 的骑士获得胜利。数据保证最后只有一个骑士获得胜利，对于每个骑士，输出打败他的骑士的编号，特别的，最后胜利的骑士输出 \(0\)。
- \(2 \le n \le 3 \cdot 10^5\)
- \(1 \le m \le 3\cdot 10^5\)
思路
这道题的关键在于快速找出 \([l,r]\) 之间还在场上的骑士。
对于每个被打败的骑士，向右边连一条边，遍历时只会在没有被打败的骑士处停下来。这里使用并查集加上路径压缩就能取得很优秀的复杂度。
要找到下一个骑士只需要继续遍历右边的一块就行，这里会把胜利的骑士也一同处理了，所以在最后把胜利的骑士的父亲再设置为自己就行了。
复杂度大约为 \(O(\alpha n)\)
具体思路在代码中有讲解。
代码
#include <bits/stdc++.h>using namespace std;const int N = 3e5+50;
int n,m,l,r,x,f[N],ans[N];
inline int Find(int x)
{if(f[x]!=x)f[x]=Find(f[x]);return f[x];
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n+1;i++)f[i]=i;while(m--){cin>>l>>r>>x;int now=Find(l); //找到第一个仍在场上的骑士while(now<=r) //超出范围就停止{ans[now]=x; //被 x 打败f[now]=now+1; //向右连边now=Find(now);//找下一个，这里要注意只能从 now 和后面的位置开始找} //如果当前为 x 的话从左边找会破坏路径，直接跳过 xf[x]=x; }for(int i=1;i<=n;i++)cout<<(i==ans[i]?0:ans[i])<<' ';cout<<'\n';return 0;
}
ABC380E 1D Bucket Tool
题意
有 \(n\) 个格子排成一行，初始时第 \(i\) 个格子的颜色为 \(i\)。有 \(q\) 次操作，操作 \(1\) 给出 \(x,c\)，将格子 \(x\) 与和 \(x\) 同色的色块染成 \(c\)。操作 \(2\) 给出 \(x\)，询问颜色为 \(x\) 的格子的数量。
- \(1\le n \le 5 \cdot 10^5\)
- \(1\le q \le 2 \cdot 10^5\)
思路
考虑用并查集怎么做。
如果当前块右边的一块的颜色与当前块相同，就把当前块的父亲设置为右边的一块。这样每次遍历停下的点就是该极色块的右端点。
对于操作 \(1\) ，先要找到最大的一块，因为可能左右两块颜色相同但是并未相连，由于每次是在右端点停，对于右边一块直接找右端点的右边一个就行，这里还要维护左端点这个信息来向左扩展。
合并两个块时，左边的块的父亲设置为右边的块，更新大小和左边界。
直到无法扩展再更新颜色，这里要记录每种颜色的块原本有多少个，然后直接加减就行。
对于操作 \(2\)，直接输出记录的数量就行。
代码
#include <bits/stdc++.h>using namespace std;const int N = 5e5+50;
int n,q,c[N],f[N],siz[N],cnt[N],L[N];
inline int Find(int x)
{if(f[x]!=x)f[x]=Find(f[x]);return f[x];
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++)c[i]=i,f[i]=i,siz[i]=1,L[i]=i,cnt[i]=1;while(q--){int op;cin>>op;if(op==1){int x,C;cin>>x>>C;int rt=Find(x);while(c[rt]==c[Find(L[rt]-1)]) //向左扩展{int to=Find(L[rt]-1);f[to]=rt; //左边合并到右边siz[rt]+=siz[to];L[rt]=L[to];} while(c[rt]==c[Find(rt+1)]) //向右扩展{int to=Find(rt+1);f[rt]=to;siz[to]+=siz[rt];L[to]=L[rt];rt=to;}cnt[c[rt]]-=siz[rt]; // 最后更新每种颜色的小块的数量cnt[C]+=siz[rt];c[rt]=C;}else{int x;cin>>x;cout<<cnt[x]<<'\n';}}return 0;
}
小结
对于区间染色，并查集做到的实际上是快速跳过已经被合并的元素来降低复杂度，对于一些区间能够合并或者是元素会被消除的题，不妨考虑一下能否使用并查集。