可持久化并查集?
具体来说就是带历史版本的并查集
也就是可持久化数组+并查集
数组我们选择用可持久化线段树来实现,并查集用按秩合并。
注意一点,$fa[p]$,$p$是线段树的编号,而不是$p$这个位置,然而$fa[p]$表示一个位置。
务必记住这一点。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=2e5+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n;
struct node{int l,r;}t[N*25];int cnt,root[N],fa[N*25],dep[N*25];
void build(int &p,int l,int r)
{
    p=++cnt;
    if(l==r){fa[p]=l;return ;}
    int mid=l+r>>1;build(t[p].l,l,mid);build(t[p].r,mid+1,r);
}
void update(int l,int r,int &x,int y,int pos,int val)
{
    t[x=++cnt]=t[y];
    if(l==r){fa[x]=val;dep[x]=dep[y];return ;}
    int mid=l+r>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos,val);
    else update(mid+1,r,t[x].r,t[y].r,pos,val);
}
void add(int p,int l,int r,int pos)
{
    if(l==r){++dep[p];return ;}
    int mid=l+r>>1;
    if(pos<=mid)add(t[p].l,l,mid,pos);
    else add(t[p].r,mid+1,r,pos);
}
int query(int p,int l,int r,int pos)
{
    if(l==r)return p;
    int mid=l+r>>1;
    if(pos<=mid)return query(t[p].l,l,mid,pos);
    else return query(t[p].r,mid+1,r,pos);
}
int get(int p,int x)//由于是按秩合并,所以没有路径压缩,也正是因为没有路径压缩,因此单次修改只用改两个集合的根
{
    int f=query(p,1,n,x);
    if(x==fa[f])return f;
    return get(p,fa[f]);
}
int main()
{
    qr(n);int m;qr(m);
    build(root[0],1,n);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int op;qr(op);
        if(op==1)
        {
            root[i]=root[i-1];
            int x,y;qr(x),qr(y);x^=ans;y^=ans;
            int p=get(root[i],x),q=get(root[i],y);
            if(fa[p]==fa[q])continue;
            if(dep[p]>dep[q])swap(p,q);
            update(1,n,root[i],root[i-1],fa[p],fa[q]);//fa[p]这个位置的父亲更新更新为fa[q]
            if(dep[p]==dep[q])add(root[i],1,n,fa[q]);//如果两个集合的最大深度相等,由于p这个集合的最大深度要+1,那么其实相当于q这个大集合的深度+1
        }
        else if(op==2){int k;qr(k);k^=ans;root[i]=root[k];}//返回历史版本
        else
        {
            root[i]=root[i-1];
            int x,y;qr(x);qr(y);x^=ans;y^=ans;
            int p=get(root[i],x),q=get(root[i],y);
            if(fa[p]==fa[q])ans=1;//x,y的父亲相等
            else ans=0;
            qw(ans);puts("");
        }
    }
    return 0;
}