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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+5;
 4 int n, m;
 5 int L[maxn*30], R[maxn*30], fa[maxn*30], dep[maxn*30];
 6 int root[maxn*30];
 7 int cnt;
 8 void build(int &rt, int l, int r) {
 9     rt = ++cnt;
10     if(l == r){
11         fa[rt] = l;
12         return ;
13     }
14     int mid = (l+r)/2;
15     build(L[rt],l,mid);
16     build(R[rt],mid+1,r);
17 }
18 void merge(int last, int &rt, int l, int r, int pos, int Fa) {
19     rt = ++cnt;
20     L[rt] = L[last], R[rt] = R[last];
21     if(l == r) {
22         fa[rt] = Fa;
23         dep[rt] = dep[last];
24         return;
25     }
26     int mid = (l+r)/2;
27     if(pos <= mid) merge(L[last],L[rt],l,mid,pos,Fa);
28     else merge(R[last],R[rt],mid+1,r,pos,Fa);
29 }
30 void update(int rt, int l, int r, int pos) {
31     if(l == r) {
32         dep[rt]++;
33         return;
34     }
35     int mid = (l+r)/2;
36     if(pos <= mid) update(L[rt],l,mid,pos);
37     else update(R[rt],mid+1,r,pos);
38 }
39 int query(int rt, int l, int r, int pos) {
40     if(l == r) return rt;
41     int mid = (l+r)/2;
42     if(pos <= mid) return query(L[rt],l,mid,pos);
43     else return query(R[rt],mid+1,r,pos);
44 }
45 int find(int rt, int pos) {
46     int now = query(rt,1,n,pos);
47     if(fa[now] == pos) return now;
48         return find(rt,fa[now]);
49 }
50 int main() {
51     scanf("%d%d",&n,&m);
52     build(root[0],1,n);
53     for(int i = 1; i <= m; i++) {
54         int op; scanf("%d",&op);
55         if (op == 1) {
56             int a, b; scanf("%d%d",&a,&b);
57             int posa, posb;
58             root[i] = root[i-1];
59             posa = find(root[i],a);
60             posb = find(root[i],b);
61             if(fa[posa] != fa[posb]) {
62                 if(dep[posa] > dep[posb]) swap(posa,posb);
63                 merge(root[i-1],root[i],1,n,fa[posa],fa[posb]);
64                 if(dep[posa] == dep[posb]) update(root[i],1,n,fa[posb]);
65             }
66         }
67         else if(op == 2) {
68             int k; scanf("%d",&k);
69             root[i] = root[k];
70         }
71         else if(op == 3) {
72             int a, b; scanf("%d%d",&a,&b);
73             root[i] = root[i-1];
74             int posa, posb;
75             posa = find(root[i],a);
76             posb = find(root[i],b);
77             if(fa[posa] == fa[posb]) puts("1");
78             else puts("0");
79         }
80     }
81     return 0;
82 }