如何用并查集解决区间染色问题的？

并查集的区间染色 并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。 在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。 以例题来做具体解释。 [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 的话从左边找会破坏路径，直接跳过 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 题意 有 \(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\)，直接输出记录的数量就行。