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 { 6int 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, mid11#define rson t[i].rs, mid + 1, r12int cnt;13void build(int &i, int l, int r) {14i = ++ cnt;15if (l == r) {t[i].fa = l; return ;}//初始时节点父亲就是自己16build(lson), build(rson);17}18void merge(int j, int &i, int l, int r, int pos1, int pos2) {19//pos1是深度较小的节点的fa ， 找到pos1的位置 ， 将该位置的fa改为pos2 ， 也就是合并操作20i = ++ cnt;21t[i] = t[j];//复制22if (l == r) {23t[i].fa = pos2;24return ;25}26if (pos1 <= mid) merge(t[j].ls, lson, pos1, pos2);27else merge(t[j].rs, rson, pos1, pos2);28}29void update(int i, int l, int r, int pos) {30if (l == r) {t[i].dep ++; return ;}31if (pos <= mid) update(lson, pos);32else update(rson, pos);33}34int query(int i, int l, int r, int pos) {//返回节点pos的编号35if (l == r) return i;36if (pos <= mid) return query(lson, pos);37else return query(rson, pos);38}39int find(int i, int pos) {//类似并查集找祖先操作40int now = query(i, 1, n, pos);41if (t[now].fa == pos) return now;//也是返回节点编号42return find(i, t[now].fa);43}44#undef mid45#undef lson46#undef rson47 }48 using namespace SegmentTree;49 int main() {50scanf("%d %d", &n, &m);51build(rt[0], 1, n);52for (int i = 1; i <= m; i ++) {53int opt, x, y;54scanf("%d %d", &opt, &x);55if(opt == 1) {//合并x, y所在集合56scanf("%d", &y);57int posx, posy;58rt[i] = rt[i - 1];//复制新版本59posx = find(rt[i], x), posy = find(rt[i], y);60if (t[posx].fa != t[posy].fa) {//按秩合并61if (t[posx].dep > t[posy].dep) swap(posx, posy);62merge(rt[i - 1], rt[i], 1, n, t[posx].fa, t[posy].fa);63if (t[posx].dep == t[posy].dep) update(rt[i], 1, n, t[posy].fa);64//避免深度相同65}66}67else if(opt == 2) rt[i] = rt[x];68else if(opt == 3) {69scanf("%d", &y);70rt[i] = rt[i - 1];71int posx, posy;72posx = find(rt[i], x), posy = find(rt[i], y);73if (t[posx].fa == t[posy].fa) puts("1");74else puts("0");75}76}77return 0;78 }【P3402 可持久化并查集】
经验总结扩展阅读
- 地铁可以提前下车出站吗
- 2021微信状态最可爱的签名大全
- 怎么让橡皮树长粗
- 平板支撑可以练什么
- 下雨天可以开窗通风吗
- 北屯到可可托海景区多少公里
- 可怜身上衣正单的下一句是什么
- c3驾照可升C2吗
- 异地可以补办户口本吗
- 黄金怎么回收?