P3402 可持久化并查集 _生活百科

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 可持久化并查集】

P3402 可持久化并查集

推荐阅读

教你如何使用迅雷离线下载[新发布]

天麻能泡白酒吗天麻可以和虫草花一起煲汤吗

皮蛋是生的还是熟的怎么判断皮蛋是生的还是熟的

我们好像在哪见过歌词我们好像在哪见过歌词歌谱

煤炭公司起名大全免费煤炭行业起名大全

如何通过女人面相看婚姻哪些面相的女人婚姻好

孕妇梦见和别人吵架孕妇梦见别人挣了很多钱

瑜伽入门动作图解瑜伽入门动作图解上

etc不抬杆可以倒回吗 etc不抬杆可以倒回会被扣分吗

一斤几克重，一斤等于多少千克

节日由来英语节日由来

忙碌了多少天辛苦了多少年是啥歌快去听一下吧

五岳奇险天下第一山是哪座山天下第一山是哪座山

“八岐之术”是什么？

关于洛阳昊远机械设备有限公司简述洛阳昊远机械设备有限公司

梦见和当官的同学在一起商人梦见当官的同学

梦见水里有黑鱼在游

在“再见阿郎”中的刘金虎怎么又是金鹏？

喝番茄汁有什么好处番茄汁的好处有哪些

商业承兑汇票是什么意思商业承兑汇票的理解