并查集

简介

基本操作

find

int find(int x) { return fa[x] == x; } 

merge

路径压缩

复杂度待证

int find(int x) { return fa[x] == x; } 

按秩合并

复杂度 $O(n\log n)$，不是均摊

复杂度待证

if (dep[x] > dep[y]) swap(x, y);
fa[x] = y; if (dep[x] == dep[y]) ++dep[y];

按大小合并

复杂度待证

if (sz[x] > sz[y]) swap(x, y);
fa[x] = y; sz[y] += sz[x]; 

undo

只是简单的撤销

while(top > _top) {
	int x = st[top--];
    fa[x] = x;
}

带权并查集

就是多记录一些东西（大概

注意一定要满足可加性（我也不知道该怎么称呼这东西

find

int find(int x) {
    if (fa[x] == x) return x;
    int fx = fa[x]; fa[x] = find(fa[x]);
    d[x] += d[fx];
    return fa[x];
}

应用

1. 每次将一个区间内的点连起来，用并查集可以做到 $O(n\alpha(n))$，其中 $n$ 的区间大小

   需要注意实数区间和整点区间要区分开

   如果是实数区间就只能这样（即 $[1,4]$ 和 $[5,10]$ 不能合并

   if (x == y) vis[x] = 1; //整点特判
   x = find(x);
   while (x < y) x = fa[x] = find(x + 1);

   如果是整点的区间（即 $[1,4]$ 和 $[5,10]$ 可以合并成 $[1, 10]$

   for (int i = 1; i <= n + 1; ++i) fa[i] = i;
   x = find(x);
   while (x <= y) x = fa[x] = find(x + 1); //[i, fa[i])

例题

1. 简要题意：给定一个包含 $0,1,?$ 的长度为 $n$ 的字符串 $S$，需要对 $k\in[1,n]$，求每次将 $S$ 中的 $?$ 变成 $0$ 或 $1$ 后的最多操作次数，对于某一个 $k$，字符串 $S$ 的一次操作为每次删掉连续 $k$ 个相同字符

   $|S|\le 10^6$

   简要题解：首先我们考虑暴力枚举答案，能够发现答案是一个调和级数，最多不超过 $O(n\log n)$

   我们考虑用并查集维护每个点右边第一个长度超过 $l$ 的连续段的起点

   随着 $l$ 的增加，我们只需要每次把向右连续段的长度刚好为 $l$ 的点的并查集向右合并即可

   时间复杂度 $O(n\alpha(n)\log n)$

   CF 1398F Controversial Rounds