洛谷 P3402 【模板】可持久化并查集

缘起

继续研究可持久化数据结构——可持久化并查集~ 洛谷 P3402 【模板】可持久化并查集

分析

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
题目描述
n个集合 m个操作

操作：

1 a b 合并a,b所在集合

2 k 回到第k次操作之后的状态(查询算作操作)

3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

输入格式
无

输出格式
无

输入输出样例
输入 #1复制
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

输出 #1复制
1
0
1

说明/提示
1 <= n <= 10w, 1 <= m <= 20w

By zky 出题人大神犇

时间限制
1s
内存限制
125MB

此题是可持久化并查集板题.

什么是可持久化并查集?

可持久化并查集就是可持久化的并查集~ 额, 好像说了和没说一样. 其实和【2】一样——就是支持历史版本回溯的并查集.

怎么实现?

这里我参阅了【1】中的思想. 秒懂~

首先你得知道如何刻画一个并查集? 【3】就知道了, f数组就可以完全刻画一个并查集. 所以可持久化并查集就是可持久化的f数组–> 可持久化的数组? 不就是【2】中研究的嘛~ 其实现是可持久化线段树, 也就是使用可持久化线段树来维护一下并查集数组f而已.

注意, 因为题目中涉及到了并查集的合并, 所以我们就要考虑一下并查集该如何合并了? 在【3】和【4】中展示了两种合并方式，【3】中是路径压缩, 而【4】使用了路径压缩+启发式合并（说的高大上，其实就是元素数目小的树的根节点的父节点改成元素数目多的树的根节点）

但是本题不能使用路径压缩. 因为【2】中的可持久化线段树是单点更新的——只有单点更新才能保证一次只有O(logn)个点新增, 从而可以使用可持久化思想，如果允许路径压缩的话, 则一次合并将导致并查集数组中N多元素的值的改变, 则要新增的点就很多了. 这就不利于使用可持久化思想.

所以本题和【2】本质上没有什么不同, 只是【2】中维护的是一个指定的数组, 而本题维护的是并查集数组而已（所以稍微麻烦一点~）.

以下代码风格和【2】保持一致，私以为代码风格保持一致是一件很重要的事情~ 不想以迥异的风格的代码来切本质相同的题目.

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL
const int maxn = 200005;
int n,m, ver[maxn], version, cnt;

struct PSTNode
{
	int begin, end, l,r,f; // f是该节点的并查集数组的值(注意, 该字段仅仅对于叶子节点才有效)
}pst[maxn*20]; // 数组一定要开大开大开大!

int newnode(int i)
{
	int root = ++cnt;
	pst[root].begin = pst[i].begin;
	pst[root].end = pst[i].end;
	pst[root].l = pst[i].l;
	pst[root].r = pst[i].r;
	return root;
}

int build(int begin, int end)
{
	int root = ++cnt;
	pst[root].begin = begin;
	pst[root].end = end;
	if (begin==end)
	{
		pst[root].f = -1; // 初始化带权并查集
		return root;
	}
	int mid = begin+end>>1;
	pst[root].l = build(begin, mid);
	pst[root].r = build(mid+1, end);
	return root;
}

int getf(int cur, int i) // 寻找i的并查集意义上的父节点, 
{
	if (pst[cur].begin==pst[cur].end)
	{
		return pst[cur].f;
	}
	int mid = pst[cur].begin + pst[cur].end>>1;
	if (i<=mid)
	{
		return getf(pst[cur].l, i);
	}
	return getf(pst[cur].r, i);
}

int getroot(int v, int i, int &tot) // 寻找版本v中的i所在并查树的根节点(其实做的挺暴力的), tot是i在版本v中的并查集意义上的树中的节点个数
{
	int fa = getf(v, i); //  找到i在版本v中的父节点fa(属于1~n)
	if (fa<0) // 说明i本身就是根节点了
	{
		tot = fa; // 注意, tot是负数
		return i;
	}
	return getroot(v, fa, tot); // 递归寻找, 注意, 这里并没有做路径压缩
}

int updata(int cur, int i, int j) // 将i的并查集值改成j
{
	if (pst[cur].begin==pst[cur].end)
	{
		int root = newnode(cur);
		pst[root].f = j; // 将i的并查集值改成j
		return root;
	}
	int mid = pst[cur].begin+pst[cur].end>>1, other, me;
	bool flag;
	if (i<=mid)
	{
		other = pst[cur].r;
		flag = false;
		me = updata(pst[cur].l, i, j);
	}
	else
	{
		other = pst[cur].l;
		flag = true;
		me = updata(pst[cur].r, i, j);
	}
	int root = newnode(cur);
	pst[root].l = flag?other:me;
	pst[root].r = flag?me:other;
	return root;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	ver[version] = build(1, n); // 伊始是版本0
	while(m--)
	{
		int op,a,b, roota, tota, rootb, totb;
		scanf("%d", &op);
		++version; // 版本自增
		switch(op)
		{
		case 1:
			scanf("%d%d",&a, &b);
			roota = getroot(ver[version-1], a, tota), rootb = getroot(ver[version-1], b, totb); // 找到两个节点在上一个版本的并查集意义上的根节点, 并且返回了两棵并查树节点的个数-tota和-totb, 注意, 传入的a,b是[1,n]中的数
			if (roota^rootb) // roota,rootb也是[1,n]中的数
			{
				if (tota>totb) // 则需要将roota并入到rootb 中去（即所谓的并查集的启发式合并）, 即整个并查集数组仅仅修改 roota的并查集数组值, 即单点更新, 可以使用可持久化思想
				{
					ver[version] = updata(ver[version-1], roota, rootb); // 改爹
					ver[version] = updata(ver[version], rootb, tota+totb); // 启发式合并, 注意, 更改树的大小一定也要开辟新节点, 不能仅仅在上面改完爹的并查集数组上改. 因为rootb可能是前一个版本的, 如果直接改的话, 就改了前一个版本的数据了
				}
				else // 则需要将rootb并入到roota中去,并且生成新的版本
				{
					ver[version] = updata(ver[version-1], rootb, roota);
					ver[version] = updata(ver[version], roota, tota+totb);
				}
			}
			else // 如果a和b原本就在一个并查集中的话
			{
				ver[version] = ver[version-1]; // 则只需要简单的将根节点指向上一个版本的根节点即可, 【2】还新开辟了一个节点, 其实没必要
			}
			break;
		case 2:
			scanf("%d", &a);
			ver[version] = ver[a]; // 简单的将第version个版本的并查集对应的线段树的根节点指向第a个版本的并查集对应的线段树的根节点即可
			break;
		case 3:
			scanf("%d%d", &a, &b);
			roota = getroot(ver[version-1], a, tota), rootb = getroot(ver[version-1], b, totb);
			(roota^rootb)?puts("0"):puts("1");
			ver[version] = ver[version-1]; // 就是简单查询一下也需要更新版本的, 不过也就是简单指一下根节点即可
			break;
		}
	}
	return 0;
}

ac情况

1
2
3
4
5
P3402 【模板】可持久化并查集
评测状态
Accepted
评测分数
100

参考

【1】https://www.cnblogs.com/cjoierljl/p/9567859.html

【2】https://yfsyfs.github.io/2019/10/15/%E6%B4%9B%E8%B0%B7-P3919-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E7%BB%84%EF%BC%88%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91-%E5%B9%B3%E8%A1%A1%E6%A0%91%EF%BC%89/

【3】https://yfsyfs.github.io/2019/05/24/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%A8%A1%E6%9D%BF/

【4】https://yfsyfs.github.io/2019/05/24/%E7%AD%89%E4%BB%B7%E7%B1%BB/