启发式合并

入门

例题

[ABC329F] Colored Ball。

• 题意

给定 \(N\) 个盒子，每个盒子里面有一个颜色为 \(C_i\) 的小球。有 \(Q\) 次操作，每次操作将第 \(a_i\) 个盒子中的球都放到第 \(b_i\) 个盒子里面，你需要在每次操作后输出当前操作结束后第 \(b_i\) 个盒子里面有多少个不同颜色的小球。

如果盒子为空，输出 \(0\) 即可。

首先看到对答案有贡献的只有小球的颜色，即种类。因此可以联想到 STL set 实现的自动去重功能。

考虑按题意模拟。若构造一组形如由极小集合合并至极大集合的数据，此算法的最劣复杂度是 \(O(nq\log n)\) 的。

此时考虑启发式合并。

我们考虑让集合中元素个数数量小的合并至大的中。此时可以证明时间复杂度是 \(O(n\log ^2 n)\) 的。

初看上可能感觉这就是个暴力。但是我们分析一下每个元素被 insert 了多少次。

一个集合中的元素被放入另一个集合中会被 insert 一次。但是这个元素所在的集合的大小至少扩大了一倍。所以一个元素最多被 insert \(O(\log n)\) 次。加上 set 本身带有的 \(O(\log n)\) 的复杂度，最终复杂度是 \(O(n\log ^2 n)\) 的。

在这里，对于两个大小不一样的集合，我们将小的集合合并到大的集合中，而不是将大的集合合并到小的集合中。

为什么呢？这个集合的大小可以认为是集合的高度（在正常情况下），而我们将集合高度小的并到高度大的显然有助于我们找到父亲。

让高度小的树成为高度较大的树的子树，这个优化可以做到单次 \(O(\log n)\)。

while(q--) {
		cin >> x >> y;
		if(s[x].size() < s[y].size()) {
			for(auto i : s[x])
				s[y].insert(i);
			s[x].clear();
			cout << s[y].size() << '\n';
		}
		else {
			for(auto i : s[y])
				s[x].insert(i);
			s[y].clear(), swap(s[x], s[y]);
			cout << s[y].size() << '\n';
		}
	}

P3201 [HNOI2009] 梦幻布丁

dsu on tree

例题

[ABC350G] Mediator

首先一个点是否与询问点对相邻，可以转换为对父亲的讨论。

下列情况是有解的：

• \(fa_u = fa_v\) 且 \(u, v\) 不是根节点，答案为 \(fa_u\)
• \(fa_{fa_u} = v\)，答案为 \(fa_u\)
• \(fa_{fa_v} = u\)，答案为 \(fa_v\)

画图分析较为移动。

于是我们只需要维护父亲即可，考虑启发式合并。

每次将连通块大小较小的合并至较大的连通块内，对于每次这种操作暴力 dfs 修改 \(fa\) 即可。

连通块大小可以用并查集轻松维护。

证明复杂度：每次连通块大小最多扩大一倍，所以复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int N = 1e5 + 5;
const int mod = 998244353;
int n, Q, u, v, op, ans, fa[N];
vector<int> g[N];

inline void dfs(int x, int last) {
	fa[x] = last;
	
	for(auto u : g[x])
		if(u != last) dfs(u, x);
	
	return ;
}

namespace USF {
	int Fa[N], sz[N];
	
	inline void init() {
		for(int i = 1 ; i < N ; ++ i)
			Fa[i] = i, sz[i] = 1;
		
		return ;
	}
	
	inline int find(int x) {
		if(x != Fa[x]) Fa[x] = find(Fa[x]);
		
		return Fa[x];
	}
	
	inline void merge(int x, int y) {
		int fx = find(x), fy = find(y);
		
		if(fx == fy) return ;
		
		if(sz[fx] < sz[fy]) swap(x, y), swap(fx, fy);
		
		dfs(y, x);
		
		sz[fx] += sz[fy], Fa[fy] = fx;
		
		g[x].pb(y), g[y].pb(x);
		
		return ;
	}
}

using namespace USF;

inline int query(int u, int v) {
	if(fa[u] == fa[v] && fa[u]) return fa[u];
	if(fa[fa[u]] == v) return fa[u];
	if(fa[fa[v]] == u) return fa[v];
	
	return 0;
}

signed main() {
	ios_base :: sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n >> Q;
	
	init();
	
	while(Q --) {
		cin >> op >> u >> v;
		
		op = 1 + ((op * (1 + ans)) % mod) % 2;
		u = 1 + ((u * (1 + ans)) % mod) % n;
		v = 1 + ((v * (1 + ans)) % mod) % n;
		
		if(op == 1) merge(u, v);
		else {
			ans = query(u, v);
			
			cout << ans << '\n';
		}
	}
	
	return 0;
}