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

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

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

以例题来做具体解释。

[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\)，直接输出记录的数量就行。

代码

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

小结

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