一类并查集维护的区间染色问题
并查集的区间染色并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。
在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。
以例题来做具体解释。
(Problem - A - Codeforces)
题意
\(n\) 个骑士编号从 \(1\) 到 \(n\)，给出 \(m\) 场决斗。每场决斗给出 \(l , r, x\) 表示区间 \(\) 之间还没被打败的骑士之间进行决斗，编号为 \(x\) 的骑士获得胜利。数据保证最后只有一个骑士获得胜利，对于每个骑士，输出打败他的骑士的编号，特别的，最后胜利的骑士输出 \(0\)。
[*]\(2 \le n \le 3 \cdot 10^5\)
[*]\(1 \le m \le 3\cdot 10^5\)
思路
这道题的关键在于快速找出 \(\) 之间还在场上的骑士。
对于每个被打败的骑士，向右边连一条边，遍历时只会在没有被打败的骑士处停下来。这里使用并查集加上路径压缩就能取得很优秀的复杂度。
要找到下一个骑士只需要继续遍历右边的一块就行，这里会把胜利的骑士也一同处理了，所以在最后把胜利的骑士的父亲再设置为自己就行了。
复杂度大约为 \(O(\alpha n)\)
具体思路在代码中有讲解。
代码
#include using namespace std;const int N = 3e5+50;int n,m,l,r,x,f,ans;inline int Find(int x){ if(f!=x)f=Find(f); return f;}int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i>l>>r>>x; int now=Find(l);//找到第一个仍在场上的骑士 while(now>C; int rt=Find(x); while(c==c-1)]) //向左扩展 { int to=Find(L-1); f=rt; //左边合并到右边 siz+=siz; L=L; } while(c==c) //向右扩展 { int to=Find(rt+1); f=to; siz+=siz; L=L; rt=to; } cnt]-=siz; // 最后更新每种颜色的小块的数量 cnt+=siz; c=C; } else { int x;cin>>x; cout
页:
[1]