P3402
通过主席树维护不同版本的并查集,注意要采用按秩合并的方式,路径压缩可能会爆。
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 3e5 + 10;
4 int n, m, rt[N * 30];
5 struct node {
6 int ls, rs, dep, fa;//fa的值都是在1~n范围中的
7 }t[N * 30];
8 namespace SegmentTree {
9 #define mid ((l + r) >> 1)
10 #define lson t[i].ls, l, mid
11 #define rson t[i].rs, mid + 1, r
12 int cnt;
13 void build(int &i, int l, int r) {
14 i = ++ cnt;
15 if (l == r) {t[i].fa = l; return ;}//初始时节点父亲就是自己
16 build(lson), build(rson);
17 }
18 void merge(int j, int &i, int l, int r, int pos1, int pos2) {
19 //pos1是深度较小的节点的fa,找到pos1的位置,将该位置的fa改为pos2,也就是合并操作
20 i = ++ cnt;
21 t[i] = t[j];//复制
22 if (l == r) {
23 t[i].fa = pos2;
24 return ;
25 }
26 if (pos1 <= mid) merge(t[j].ls, lson, pos1, pos2);
27 else merge(t[j].rs, rson, pos1, pos2);
28 }
29 void update(int i, int l, int r, int pos) {
30 if (l == r) {t[i].dep ++; return ;}
31 if (pos <= mid) update(lson, pos);
32 else update(rson, pos);
33 }
34 int query(int i, int l, int r, int pos) {//返回节点pos的编号
35 if (l == r) return i;
36 if (pos <= mid) return query(lson, pos);
37 else return query(rson, pos);
38 }
39 int find(int i, int pos) {//类似并查集找祖先操作
40 int now = query(i, 1, n, pos);
41 if (t[now].fa == pos) return now;//也是返回节点编号
42 return find(i, t[now].fa);
43 }
44 #undef mid
45 #undef lson
46 #undef rson
47 }
48 using namespace SegmentTree;
49 int main() {
50 scanf("%d %d", &n, &m);
51 build(rt[0], 1, n);
52 for (int i = 1; i <= m; i ++) {
53 int opt, x, y;
54 scanf("%d %d", &opt, &x);
55 if(opt == 1) {//合并x, y所在集合
56 scanf("%d", &y);
57 int posx, posy;
58 rt[i] = rt[i - 1];//复制新版本
59 posx = find(rt[i], x), posy = find(rt[i], y);
60 if (t[posx].fa != t[posy].fa) {//按秩合并
61 if (t[posx].dep > t[posy].dep) swap(posx, posy);
62 merge(rt[i - 1], rt[i], 1, n, t[posx].fa, t[posy].fa);
63 if (t[posx].dep == t[posy].dep) update(rt[i], 1, n, t[posy].fa);
64 //避免深度相同
65 }
66 }
67 else if(opt == 2) rt[i] = rt[x];
68 else if(opt == 3) {
69 scanf("%d", &y);
70 rt[i] = rt[i - 1];
71 int posx, posy;
72 posx = find(rt[i], x), posy = find(rt[i], y);
73 if (t[posx].fa == t[posy].fa) puts("1");
74 else puts("0");
75 }
76 }
77 return 0;
78 }
Shell
标签:
留言评论