一类并查集维护的区间染色问题

并查集的区间染色

并查集作为一种高级数据结构，可以高效地维护元素与元素，元素与集合之间的关系。
在一些涉及到区间染色的题中，并查集可以很好地维护块的大小，块的边界和块的合并。
以例题来做具体解释。
[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)\)
具体思路在代码中有讲解。
代码

[code]#include 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>l>>r>>x;        int now=Find(l);  //找到第一个仍在场上的骑士        while(now>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