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

并查集的区间染色并查集作为一种高级数据结构可以高效地维护元素与元素元素与集合之间的关系。在一些涉及到区间染色的题中并查集可以很好地维护块的大小块的边界和块的合并。以例题来做具体解释。[CF356A Knight Toumament](Problem - A - Codeforces)题意 个骑士编号从 1 到 给出 场决斗。每场决斗给出 ,, 表示区间 [,] 之间还没被打败的骑士之间进行决斗编号为 的骑士获得胜利。数据保证最后只有一个骑士获得胜利对于每个骑士输出打败他的骑士的编号特别的最后胜利的骑士输出 0。2≤≤3⋅1051≤≤3⋅105思路这道题的关键在于快速找出 [,] 之间还在场上的骑士。对于每个被打败的骑士向右边连一条边遍历时只会在没有被打败的骑士处停下来。这里使用并查集加上路径压缩就能取得很优秀的复杂度。要找到下一个骑士只需要继续遍历右边的一块就行这里会把胜利的骑士也一同处理了所以在最后把胜利的骑士的父亲再设置为自己就行了。复杂度大约为 ()具体思路在代码中有讲解。代码#include bits/stdc.husing namespace std;const int N 3e550;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);cinnm;for(int i1;in1;i)f[i]i;while(m--){cinlrx;int nowFind(l); //找到第一个仍在场上的骑士while(nowr) //超出范围就停止{ans[now]x; //被 x 打败f[now]now1; //向右连边nowFind(now);//找下一个这里要注意只能从 now 和后面的位置开始找} //如果当前为 x 的话从左边找会破坏路径直接跳过 xf[x]x;}for(int i1;in;i)cout(ians[i]?0:ans[i]) ;cout\n;return 0;}ABC380E 1D Bucket Tool题意有 个格子排成一行初始时第 个格子的颜色为 。有 次操作操作 1 给出 ,将格子 与和 同色的色块染成 。操作 2 给出 询问颜色为 的格子的数量。1≤≤5⋅1051≤≤2⋅105思路考虑用并查集怎么做。如果当前块右边的一块的颜色与当前块相同就把当前块的父亲设置为右边的一块。这样每次遍历停下的点就是该极色块的右端点。对于操作 1 先要找到最大的一块因为可能左右两块颜色相同但是并未相连由于每次是在右端点停对于右边一块直接找右端点的右边一个就行这里还要维护左端点这个信息来向左扩展。合并两个块时左边的块的父亲设置为右边的块更新大小和左边界。直到无法扩展再更新颜色这里要记录每种颜色的块原本有多少个然后直接加减就行。对于操作 2直接输出记录的数量就行。代码#include bits/stdc.husing namespace std;const int N 5e550;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);cinnq;for(int i1;in;i)c[i]i,f[i]i,siz[i]1,L[i]i,cnt[i]1;while(q--){int op;cinop;if(op1){int x,C;cinxC;int rtFind(x);while(c[rt]c[Find(L[rt]-1)]) //向左扩展{int toFind(L[rt]-1);f[to]rt; //左边合并到右边siz[rt]siz[to];L[rt]L[to];}while(c[rt]c[Find(rt1)]) //向右扩展{int toFind(rt1);f[rt]to;siz[to]siz[rt];L[to]L[rt];rtto;}cnt[c[rt]]-siz[rt]; // 最后更新每种颜色的小块的数量cnt[C]siz[rt];c[rt]C;}else{int x;cinx;coutcnt[x]\n;}}return 0;}小结对于区间染色并查集做到的实际上是快速跳过已经被合并的元素来降低复杂度对于一些区间能够合并或者是元素会被消除的题不妨考虑一下能否使用并查集。