bzoj3673 可持久化并查集

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<iostream>
 6 
 7 using namespace std;
 8 
 9 template<typename Q> Q &read(Q &x) {
10     static char c, f;
11     for(f = 0; c = getchar(), !isdigit(c); ) if(c == ‘-‘) f = 1;
12     for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - ‘0‘;
13     if(f) x = -x; return x;
14 }
15 template<typename Q> Q read() {
16     static Q x; read(x); return x;
17 }
18 
19 const int N = 20000 + 10;
20 
21 struct Node *newnode(int, Node *, Node *);
22 
23 struct Node {
24     int v;
25     Node *ch[2];
26     int query(int l, int r, int k) {
27         if(l == r) return v;
28         int mid = (l + r) >> 1;
29         if(k <= mid) return ch[0]->query(l, mid, k);
30         else return ch[1]->query(mid + 1, r, k);
31     }
32     Node *modify(int l, int r, int k, int w) {
33         if(l == r) return newnode(w, 0, 0);
34         int mid = (l + r) >> 1;
35         if(k <= mid) return newnode(0, ch[0]->modify(l, mid, k, w), ch[1]);
36         return newnode(0, ch[0], ch[1]->modify(mid + 1, r, k, w));
37     }
38 }pool[N * 40], *pis = pool;
39 
40 Node *newnode(int v, Node *lc, Node *rc) {
41     pis->v = v, pis->ch[0] = lc, pis->ch[1] = rc;
42     return pis++;
43 }
44 
45 int n, now, tot;
46 
47 struct parr {
48     Node *root[N];
49     parr() {
50         root[0] = newnode(0, pis, pis);
51     }
52     int get(int k) const {
53         return root[now]->query(1, n, k);
54     }
55     void modify(int k, int w) {
56         root[tot] = root[now]->modify(1, n, k, w);
57     }
58 }sz, fa;
59 
60 int find(int x) {
61     int y;
62     while(x)
63         x = fa.get(y = x);
64     return y;
65 }
66 
67 void unite(int x, int y) {
68     ++tot;
69     x = find(x), y = find(y);
70     if(x == y) return;
71     int sx = sz.get(x), sy = sz.get(y);
72     if(sx < sy) swap(x, y), swap(sx, sy);
73     fa.modify(y, x);
74     sz.modify(x, sx + sy);
75     now = tot;
76 }
77 
78 int version[N];
79 int main() {
80 #ifdef DEBUG
81     freopen("in.txt", "r", stdin);
82     freopen("out.txt", "w", stdout);
83 #endif
84     
85     int m; read(n), read(m);
86     for(int i = 1; i <= m; i++) {
87         int opt = read<int>();
88         if(opt == 1) unite(read<int>(), read<int>());
89         if(opt == 2) now = version[read<int>()];
90         if(opt == 3) printf("%d\n", find(read<int>()) == find(read<int>()));
91         version[i] = now;
92     }
93     
94     return 0;
95 }