bzoj 3673: 可持久化并查集 by zky

题意

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0

题解

之前用rope水过这道题
今天来学习一下正确的可持久化并查集的姿势
其实就是普通的并查集套上一个支持可持久化的结构
一般大家比较熟悉的且支持可持久化的就是线段树了
于是我们只需要把数组写成线段树的形式
然后可持久化按线段树来写，并查集按并查集来写就可以了
时间复杂度比正常的并查集多一个log，感觉还是跑得挺快的
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=20005;
int n,m;
int rt[N],s1[N*30],s2[N*30],c[N*30];
int num=0;
void bt (int &now,int l,int r)
{
    now=++num;
    if (l==r)   {c[now]=l;return ;}
    int mid=(l+r)>>1;
    bt(s1[now],l,mid);bt(s2[now],mid+1,r);
}
int find (int now,int l,int r,int x)
{
    if (l==r) return c[now];
    int mid=(l+r)>>1;
    if (x<=mid) return find(s1[now],l,mid,x);
    else return find(s2[now],mid+1,r,x);
}
void change (int now,int &Rt,int l,int r,int x,int val)
{
    Rt=++num;
    if (l==r)   {c[Rt]=val;return ;}
    int mid=(l+r)>>1;
    s1[Rt]=s1[now];s2[Rt]=s2[now];
    if (x<=mid) change(s1[now],s1[Rt],l,mid,x,val);
    else change(s2[now],s2[Rt],mid+1,r,x,val);
}
int find_fa (int &now,int x)
{
    int fa=find(now,1,n,x);
    if (fa==x) return x;
    else
    {
        int ff=find_fa(now,fa);
        change(now,now,1,n,x,ff);
        return ff;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    bt(rt[0],1,n);
    for (int u=1;u<=m;u++)
    {
        int op;
        scanf("%d",&op);
        if (op==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int xx=find_fa(rt[u-1],x),yy=find_fa(rt[u-1],y);
            if (xx==yy) rt[u]=rt[u-1];
            else change(rt[u-1],rt[u],1,n,xx,yy);
        }
        if (op==2)
        {
            int x;
            scanf("%d",&x);
            rt[u]=rt[x];
        }
        if (op==3)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int fx=find_fa(rt[u-1],x),fy=find_fa(rt[u-1],y);
            if (fx==fy) printf("1\n");
            else printf("0\n");
            rt[u]=rt[u-1];
        }
    }
    return 0;
}