(Zerojudge) b412: 【記憶中】之記憶中的并查集 [可持久化並查集]

https://zerojudge.tw/ShowProblem?problemid=b412

使用黑魔法rope XD

其實可用可持久化線段樹

有啟發式合併 + 路徑壓縮XD

#include <iostream>
#include <stdio.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

const int MAX_N = 1e5 + 6;

rope<int> *p[MAX_N],*sz[MAX_N];
int pp[MAX_N],szz[MAX_N];

int Find(int ver,int x) {
    int ret;
    if (p[ver]->at(x) == x) return x;
    ret = Find(ver,p[ver]->at(x));
    if (p[ver]->at(x) == ret) return ret;
    p[ver]->replace(x,ret);
    return ret;
}

void Union(int ver,int x,int y) {
    x = Find(ver,x);
    y = Find(ver,y);
    if (x==y) return;
    if (sz[ver]->at(x) > sz[ver]->at(y)) {
        sz[ver]->replace(x,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(y,x);
    }
    else {
        sz[ver]->replace(y,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(x,y);
    }
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    int ans=0;
    for (int i=0;n>=i;i++) {
        pp[i] = i;
        szz[i] = 1;
    }
    n+=3;
    p[0] = new rope<int>(pp,pp+n+1);
    sz[0]= new rope<int>(szz,szz+n+1);
    for (int i=1;m>=i;i++) {
        int a;
        scanf("%d",&a);
        a^=ans;
        if (a==0) {  //go to history version
            int b;
            scanf("%d",&b);
            b^=ans;
            p[i] = p[b];
            sz[i]=sz[b];
        }
        else if (a==1) {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            Union(i,b,c);
        }
        else {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            ans = (Find(i,b) == Find(i,c));
            printf("%d\n",ans);
        }
    }
}