题目描述

有 $n$ 个集合，$m$ 个操作，操作分为三种：

1 a b ——合并 $a,b$ 所在集合;
2 k ——回到输入的第 $k$ 次操作之后的状态;
3 a b ——询问 $a,b$ 是否属于同一集合，是则输出 1 否则输出 0。

样例输入

5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2

样例输出

1
0
1

今天写完代码发现一遍过了，十分欣喜，于是有了这篇题解。

首先我们思考，如果不存在操作 $2$，那么这是一个很简单的并查集模板题。

在普通的并查集中，我们需要以下基础操作：

1. 寻找某个节点所在集合的代表节点。
2. 合并两个集合。

我们继续思考，对于并查集来说，什么是最重要的呢？

我们可以发现，对于并查集的每个操作，一定会出现 $fa$ 数组，即每个节点的父亲节点。也就是说，只要能够维护一个可持久化的 $fa$ 数组，我们就已经完成一半了。

（不懂可持久化数组的人戳这里学习

那么我们就可以考虑使用可持久化数组来维护 $fa$。

众所周知，可持久化数组是用可持久化线段树来实现的，而一般的可持久化线段树是难以维护区间修改的。

然而，在一般的并查集题目中，我们使用的是路径压缩优化，这会导致 $fa$ 有多个位置被修改，难以维护。所以我们要放弃路径压缩。

但是我们也不能不加优化，不然肯定会 TLE。所以，我们使用按秩合并的优化方法。

按秩合并的意思通常是以下两个之一：

1. 合并时将节点数量多的集合的代表节点，作为节点数量少的集合的代表节点的父亲节点。
2. 与上面大致相同，将“数量多”改为“深度大”。

在这里我采用第一种。单独采用按秩合并的并查集，寻找父亲节点操作的均摊复杂度为 $O(\log n)$。

那么我们发现还要维护一个 $Size$ 数组，所以需要两个可持久化数组。

讨论完了维护方法，我们来讨论具体实现。

设第 $i$ 次操作后的 $fa$ 根节点的编号为 $RootFa_i$，$Size$ 根节点的编号为 $RootSize_i$。

对于操作一，可以看作将 $fa$ 进行一次单点修改，对 $Size$ 进行一次单点增加。此时创建了一个新版本的 $fa$ 和 $Size$。

对于操作二，直接令 $RootFa_i=RootFa_k$，$RootSize_i=RootSize_k$。

对于操作三，查询 $a$ 所在集合和 $b$ 所在集合的代表元素是否相同，并令 $RootFa_i=RootFa_{i-1}$，$RootSize_i=RootSize_{i-1}$。

这三个操作应该不难理解。

以下是代码实现：

#include<iostream>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m,t_fa,t_size;
int root_fa[M],root_size[M];

struct SgmTree{
    int lc,rc;
    int val;
}fa[M*40],Size[M*40];

int build_fa(int l,int r){
    int p=++t_fa;
    if(l==r){
        fa[p].val=l;
        return p;
    }
    int mid=(l+r)>>1;
    fa[p].lc=build_fa(l,mid);
    fa[p].rc=build_fa(mid+1,r);
    return p;
}

int build_size(int l,int r){
    int p=++t_size;
    if(l==r){
        Size[p].val=1;
        return p;
    }
    int mid=(l+r)>>1;
    Size[p].lc=build_size(l,mid);
    Size[p].rc=build_size(mid+1,r);
    return p;
}

int add(int now,int l,int r,int x,int val){
    int p=++t_size;
    Size[p]=Size[now];
    if(l==r){
        Size[p].val+=val;
        return p;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        Size[p].lc=add(Size[now].lc,l,mid,x,val);
    }
    else{
        Size[p].rc=add(Size[now].rc,mid+1,r,x,val);
    }
    return p;
}

int change(int now,int l,int r,int x,int val){
    int p=++t_fa;
    fa[p]=fa[now];
    if(l==r){
        fa[p].val=val;
        return p;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        fa[p].lc=change(fa[now].lc,l,mid,x,val);
    }
    else{
        fa[p].rc=change(fa[now].rc,mid+1,r,x,val);
    }
    return p;
}

int query_fa(int now,int l,int r,int x){
    if(l==r){
        return fa[now].val;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        return query_fa(fa[now].lc,l,mid,x);
    }
    else{
        return query_fa(fa[now].rc,mid+1,r,x);
    }
}

int query_size(int now,int l,int r,int x){
    if(l==r){
        return Size[now].val;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        return query_size(Size[now].lc,l,mid,x);
    }
    else{
        return query_size(Size[now].rc,mid+1,r,x);
    }
}

int find_fa(int now,int i){
    int f=query_fa(root_fa[now],1,n,i);
    if(f==i){
        return i;
    }
    return find_fa(now,f);
}

void Merge(int op,int now,int x,int y){
    x=find_fa(now,x);
    y=find_fa(now,y);
    int sx=query_size(root_size[now],1,n,x),sy=query_size(root_size[now],1,n,y);
    if(sx<sy){
        root_fa[op]=change(root_fa[now],1,n,x,y);
        root_size[op]=add(root_size[now],1,n,y,sx);
    }
    else{
        root_fa[op]=change(root_fa[now],1,n,y,x);
        root_size[op]=add(root_size[now],1,n,x,sy);
    }
}

int main(){
    cin>>n>>m;
    root_fa[0]=build_fa(1,n);
    root_size[0]=build_size(1,n);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            Merge(i,i-1,x,y);
        }
        if(op==2){
            int k;
            cin>>k;
            root_fa[i]=root_fa[k];
            root_size[i]=root_size[k];
        }
        if(op==3){
            int x,y;
            cin>>x>>y;
            cout<<(find_fa(i-1,x)==find_fa(i-1,y))<<endl;
            root_fa[i]=root_fa[i-1];
            root_size[i]=root_size[i-1];
        }
    }
    return 0;
}