欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-02 19:44:40
...

题意

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;
}