【主席树】可持久化并查集加强版

线段树

传送门：BZOJ3674

首先，不要看了题就以为是可持久化并查集（假的）

这道题说白了就是一个可持久化的数组（没毛病），并查集就是数组嘛！

用主席树来模拟数组，只在叶子节点存放值，修改就新建一条链，这样叶子节点就形成了一个数组。

于是就各种复制并查集操作。

代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,op,x,y,last,tot;
int fa[8000030],ls[8000030],rs[8000030],deep[8000030],root[200030];
void build(int l,int r,int &cur){
	cur=++tot;
	if (l==r){fa[cur]=l; deep[cur]=1; return;}
	int mid=(l+r)>>1;
	build(l,mid,ls[cur]);
	build(mid+1,r,rs[cur]);
}
void modify(int l,int r,int &cur,int cur2,int x,int y){
	cur=++tot;;
	if (l==r){fa[cur]=y; return;}
	int mid=(l+r)>>1;
	if (x<=mid){modify(l,mid,ls[cur],ls[cur2],x,y); rs[cur]=rs[cur2];}
	else{modify(mid+1,r,rs[cur],rs[cur2],x,y); ls[cur]=ls[cur2];}
}
int query(int l,int r,int cur,int x){
	if (l==r) return cur;
	int mid=(l+r)>>1;
	return (x<=mid)?query(l,mid,ls[cur],x):query(mid+1,r,rs[cur],x);
}
int gfa(int x,int cur){
	int p=query(1,n,cur,x);
	if (fa[p]==x) return p;
	return gfa(fa[p],cur);
}
void add(int l,int r,int cur,int y){
	if (l==r){deep[cur]++; return;}
	int mid=(l+r)>>1;
	if (y<=mid) add(l,mid,ls[cur],y);
	else add(mid+1,r,rs[cur],y);
}
int main(){
	scanf("%d%d",&n,&m);
	
	build(1,n,root[0]);
	for (int i=1;i<=m;i++){
		scanf("%d",&op);
		if (op==1){
			root[i]=root[i-1];
			scanf("%d%d",&x,&y); x^=last; y^=last;
			x=gfa(x,root[i]); y=gfa(y,root[i]);
			if (fa[x]==fa[y]) continue;
			if (deep[x]>deep[y]) swap(x,y);
			modify(1,n,root[i],root[i-1],fa[x],fa[y]);
			if (deep[x]==deep[y]) add(1,n,root[i],fa[y]);
		}
		if (op==2){
			scanf("%d",&x); x^=last;
			root[i]=root[x];
		}
		if (op==3){
			root[i]=root[i-1];
			scanf("%d%d",&x,&y); x^=last; y^=last;
			x=gfa(x,root[i]); y=gfa(y,root[i]);
			if (fa[x]==fa[y]){last=1; puts("1");}
			else{last=0; puts("0");}
		}
	}
	
	return 0;
}