并查集的区间染色

并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。

在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。

以例题来做具体解释。

[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;
	}

小结

对于区间染色，并查集做到的实际上是快速跳过已经被合并的元素来降低复杂度，对于一些区间能够合并或者是元素会被消除的题，不妨考虑一下能否使用并查集。