可持久并查集

前置知识：主席树、可持久化数组

作用：保存历史的集合版本，查询过去版本

空间复杂度>=(klog(n)+2^log(n)^-1) [一般开40倍原空间]

详细讲解

大致过程

将fa数组和dep数组可持久化，fa数组就有了各个版本不同的值，如果开结构体的话只需要将fa定义成结构体类型，因为两个数组可持久化后下标是相同的，需要注意的是不能路径压缩，一定要按秩合并！

题目

洛谷模板

image-20210426204636666

题意

给定n个集合，每一个集合初始只有自己一个数，接下来m次操作，每次操作有三种选择，合并a和b，回到k版本，询问a和b是否属于一个集合

解法

将fa数组和dep数组可持久化，需要注意的是一定不能路径压缩，因为每次要保存版本，只是拉出来一条链，压缩路径的话就会影响其他版本的fa数组值，例如现在高版本压缩了一次路径，低版本的fa数组值被改变了，之后查询低版本时就会出错！如果没有了路径压缩那么时间就会慢很多，所以一定要按秩合并来优化一下，为什么按秩合并会快一点呢？

image-20210426213034161

看这个图，倘若询问2和4是否在一个集合，第一个畸形图就需要多往上走两步，而第二个图就可以省下些时间。

CODE

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
#include <bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int ls,rs,val;
}fa[MAXN*40];  
int dep[MAXN*40],rt[MAXN*40];
int n,m,op,a,b,tot,k;
int build(int l,int r){  
	int root=++tot;
	if(l==r){
		fa[root].val=l;  //初始fa数组值为本身
		return root;
	}
	int mid=(l+r)>>1;
	fa[root].ls=build(l,mid);
	fa[root].rs=build(mid+1,r);
	return root;
}
int query(int nod,int l,int r,int x){  //查询x在这个版本的fa数组下标
	if(l==r) return nod;
	int mid=l+r>>1;
	if(x<=mid) return query(fa[nod].ls,l,mid,x);  //在左子树上
	else return query(fa[nod].rs,mid+1,r,x);
}
int find(int nod,int x){
	int now=query(nod,1,n,x);  //查询x点在这个版本中fa数组的下标
	if(fa[now].val==x) return now;  //如果x的父亲值就是x说明x就是祖先
	return find(nod,fa[now].val);  //否则就继续找
}
int remerge(int pre,int l,int r,int x,int y){
	int root=++tot;
	fa[root]=fa[pre];  //合并时需要创建一个新版本
	if(l==r){
		fa[root].val=y;  //更新这个位置的父亲值
		return root;
	}
	int mid=l+r>>1;
	if(x<=mid) fa[root].ls=remerge(fa[pre].ls,l,mid,x,y);
	else fa[root].rs=remerge(fa[pre].rs,mid+1,r,x,y);
	return root;
}
int main(){
	ios;
	cin>>n>>m;
	rt[0]=build(1,n);  //初始化fa数组
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>a>>b;
			rt[i]=rt[i-1];  //一定不能少了这一句，之前我就是想着remerge里面已经创建当前版本了，所以这一句没必要，但是如果两个点已经在一个集合里了，下面的if就不会执行，当前版本就没有保存
			int x=find(rt[i],a),y=find(rt[i],b);  //查询a和b在当前版本的祖先
			if(fa[x].val!=fa[y].val){  
				if(dep[x]>dep[y]) swap(x,y);  //按秩合并
				rt[i]=remerge(rt[i-1],1,n,fa[x].val,fa[y].val);  //保存版本
				if(dep[x]==dep[y]) dep[y]++;  //如果两个集合高度相同的话，合并后父集合高度要加一
			}
		}
		else if(op==2){
			cin>>k;
			rt[i]=rt[k];  //回到k版本
		}
		else if(op==3){
			cin>>a>>b;
			rt[i]=rt[i-1];  //新建版本
			int fx=find(rt[i],a),fy=find(rt[i],b);  //查询
			if(fx==fy) cout<<1<<'\n';
			else cout<<0<<'\n';
		}
	}
	return 0;
}