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 可持久化并查集】
推荐阅读
- 可持久化数组 P3919 【模板】可持久化线段树 1
- 欧莱雅小蜜罐面霜敏感肌可以用吗_欧莱雅小蜜罐面霜适合什么肤质
- VideoPipe可视化视频结构化框架开源了!
- 小米平板5pro可以插卡吗_小米平板5pro可以打电话吗
- ARC148游记
- MySQL用户也可以是个角色
- steam怎么退款(steam激活码可以退款吗)
- steam退款如何操作(steam捆绑包可以退款吗)
- steam游戏怎么申请退款理由(steam捆绑包可以退款吗)
- steam如何强制退款(steam上可以退款吗)