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 }
标签:rt,P3402,持久,int,查集,fa,posx,posy,pos1 From: https://www.cnblogs.com/YHxo/p/16760609.html