Dyd's Blog

He who has a strong enough why can bear almost any how.

启发式合并

Posted on Edited on In
Symbols count in article: 3.1k Reading time ≈ 3 mins.

聪明的合并

启发式合并

其实我们很早就接触过启发式合并了，比如并查集的按秩合并就是一种启发式合并（虽然基本没用过），但还是单独提一提

定义

在解决问题时，我们常常要用到“合并”操作，而该操作是可以满足交换律的（即可以把 $a$ 合并到 $b$ 里面，也可以把 $b$ 合并到 $a$ 里面），这个时候我们可以通过一些额外的信息（如安秩合并中的秩）来决定合并的顺序，从而降低时间复杂度

例题1

[HNOI2009] 梦幻布丁

对于每种颜色，用一个集合维护其下标，每次操作就是合并两个集合，合并完后颜色的段数是不会增加的，考虑如何维护段数，设合并颜色 $a$ 和颜色 $b$ ，枚举颜色 $a$ 的所有下标，若它左右的颜色中有 $x(0 \le x \le 2)$ 个颜色是 $b$ ，就让段数减 $x$

不难发现暴力合并时间复杂度为 $O(mn)$ ，无法接受，考虑启发式合并，每次让小的集合合并到大的集合中

要用启发式合并，我们首先要解决一个问题：合并操作是满足交换律的吗？当然没有那么简单，由于操作是“把颜色 $a$ 变成颜色 $b$ ”，交换就成了“把颜色 $b$ 变成颜色 $a$ ”，当然不行

但是可以通过转化让其满足交换律吗？考虑用链表存储集合，那么只需要将表头映射一下，交换一下颜色即可，总的时间复杂度期望为 $O(n \log n)$ （然而可以被hack，但可以过题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, A = 1e6 + 5;
int n, m;
int h[A], idx;
struct Edge
{
	int ne, ver;
} e[N];
int c[N], si[A], p[A];
int ans;
void add(int x, int y)
{
	e[idx] = (Edge){h[x], y}, h[x] = idx++;
}
void merge(int &x, int &y)
{
	if (x == y)
		return;
	if (si[x] > si[y])
		swap(x, y);
	for (int i = h[x], z; i != -1; i = e[i].ne)
	{
		z = e[i].ver;
		ans -= (c[z + 1] == y) + (c[z - 1] == y);
	}
	for (int i = h[x], z; i != -1; i = e[i].ne)
	{
		c[e[i].ver] = y;
		if (e[i].ne == -1)
		{
			e[i].ne = h[y], h[y] = h[x];
			break;
		}
	}
	si[y] += si[x];
	h[x] = -1, si[x] = 0;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < A; ++i)
		h[i] = -1, p[i] = i;
	idx = ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &c[i]);
		if (c[i] != c[i - 1])
			++ans;
		add(c[i], i);
	}
	int op, x, y;
	while (m--)
	{
		scanf("%d", &op);
		if (op == 2)
			printf("%d\n", ans);
		else
		{
			scanf("%d%d", &x, &y);
			merge(p[x], p[y]);
		}
	}
	return 0;
}

例题2

Lomsat gelral

其实是一道树上并查集，类似树链剖分找出重儿子，暴力计算每一棵子树，但最后再计算重儿子，这样可以把重儿子的信息保留下来，下一次用的时候就不必再算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
int n;
int h[N], idx;
struct Edge
{
	int ne, ver;
} e[N << 1];
int c[N], cnt[N], mx;
LL ans[N], sum;
int si[N], h_son[N];
void add(int x, int y)
{
	e[idx] = (Edge){h[x], y}, h[x] = idx++;
}
void dfs1(int x, int fa)
{
	si[x] = 1;
	for (int i = h[x], y; i != -1; i = e[i].ne)
	{
		y = e[i].ver;
		if (y == fa)
			continue;
		dfs1(y, x);
		si[x] += si[y];
		if (si[y] > si[h_son[x]])
			h_son[x] = y;
	}
}
void update(int x, int fa, int dt, int pass)
{
	int _c = c[x];
	cnt[_c] += dt;
	if (cnt[_c] > mx)
		mx = cnt[_c], sum = _c;
	else if (cnt[_c] == mx)
		sum += _c;
	for (int i = h[x], y; i != -1; i = e[i].ne)
	{
		y = e[i].ver;
		if (y == fa || y == pass)
			continue;
		update(y, x, dt, pass);
	}
}
void dfs(int x, int fa, int op)
{
	for (int i = h[x], y; i != -1; i = e[i].ne)
	{
		y = e[i].ver;
		if (y == fa || y == h_son[x])
			continue;
		dfs(y, x, 0);
	}
	if (h_son[x])
		dfs(h_son[x], x, 1);
	update(x, fa, 1, h_son[x]);
	ans[x] = sum;
	if (!op)
		update(x, fa, -1, 0), mx = sum = 0;
}
int main()
{
	scanf("%d%d", &n);
	for (int i = 1; i <= n; ++i)
		h[i] = -1;
	idx = 0;
	for (int i = 1; i <= n; ++i)
		scanf("%d", &c[i]);
	for (int i = 1, u, v; i < n; ++i)
	{
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dfs1(1, -1);
	dfs(1, -1, 1);
	for (int i = 1; i <= n; i++)
		printf("%lld ", ans[i]);
	return 0;
}