并查集的区间染色
并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。
在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。
以例题来做具体解释。
[CF356A Knight Toumament](Problem - A - Codeforces)
题意
� 个骑士编号从 1 到 �，给出 � 场决斗。每场决斗给出 �,�,� 表示区间 [�,�] 之间还没被打败的骑士之间进行决斗，编号为 � 的骑士获得胜利。数据保证最后只有一个骑士获得胜利，对于每个骑士，输出打败他的骑士的编号，特别的，最后胜利的骑士输出 0。
- 2≤�≤3⋅105
- 1≤�≤3⋅105
思路
这道题的关键在于快速找出 [�,�] 之间还在场上的骑士。
对于每个被打败的骑士，向右边连一条边，遍历时只会在没有被打败的骑士处停下来。这里使用并查集加上路径压缩就能取得很优秀的复杂度。
要找到下一个骑士只需要继续遍历右边的一块就行，这里会把胜利的骑士也一同处理了，所以在最后把胜利的骑士的父亲再设置为自己就行了。
复杂度大约为 �(��)
具体思路在代码中有讲解。
代码
#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 的话从左边找会破坏路径，直接跳过 x |
f[x]=x; |
} |
for(int i=1;i<=n;i++)cout<<(i==ans[i]?0:ans[i])<<' '; |
cout<<'\n'; |
return 0; |
} |
ABC380E 1D Bucket Tool
题意
有 � 个格子排成一行，初始时第 � 个格子的颜色为 �。有 � 次操作，操作 1 给出 �,�，将格子 � 与和 � 同色的色块染成 �。操作 2 给出 �，询问颜色为 � 的格子的数量。
- 1≤�≤5⋅105
- 1≤�≤2⋅105
思路
考虑用并查集怎么做。
如果当前块右边的一块的颜色与当前块相同，就把当前块的父亲设置为右边的一块。这样每次遍历停下的点就是该极色块的右端点。
对于操作 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; |
} |
小结
对于区间染色，并查集做到的实际上是快速跳过已经被合并的元素来降低复杂度，对于一些区间能够合并或者是元素会被消除的题，不妨考虑一下能否使用并查集。
