可持久化并查集 by zky

zz:https://www.cnblogs.com/cjoierljl/p/9567859.html

https://www.cnblogs.com/peng-ym/p/9357220.html

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

0<n,m<=2*10^4

Sample Input

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

Sample Output

1
0
1

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#include<stack>

#include<vector>

#define lst long long

#define ldb long double

#define N 200050

#define lson ljl[now].ls

#define rson ljl[now].rs

using namespace std;

const int Inf=1e9;

int read()

{

    int s=0,m=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int n,Q,tot;

int dep[N*30],fa[N*30];

int Edi[N];//版本编号

struct TREE{int ls,rs;}ljl[N*30];

//主席树部分

void Build(int &now,int le,int ri)

{

    if(!now)now=++tot;

    if(le==ri)

	{

		fa[now]=le;//第now个结点属于第le个集合

		return;

	}//并查集初始化

    int mid=(le+ri)>>1;

    Build(lson,le,mid);

	Build(rson,mid+1,ri);

}

void Update(int &now,int pre,int le,int ri,int loc,int ff)

//now代表新开线段树,pre是上一个线段树对应结点的编号

//loc及ff,是指将loc并到ff这个集合中

{

    now=++tot;//新开log个节点

    if(le==ri)

    {

        dep[now]=dep[pre];//copy过来

        fa[now]=ff;//第now个结点属于ff集合

		return;

    }

    lson=ljl[pre].ls,rson=ljl[pre].rs;//把前面的树“复制”过来

    int mid=(le+ri)>>1;

    if(loc<=mid)

	    Update(lson,ljl[pre].ls,le,mid,loc,ff);

    else

	     Update(rson,ljl[pre].rs,mid+1,ri,loc,ff);

}

int Query(int now,int le,int ri,int loc)

{//查到loc这个集合，在目前这个线段中的结点编号

    if(le==ri)

	   return now;

    int mid=(le+ri)>>1;

    if(loc<=mid)

	    return Query(lson,le,mid,loc);

    else

	    return Query(rson,mid+1,ri,loc);

}

void add(int now,int le,int ri,int loc)

{//按秩合并的树高改变

    if(le==ri)

	{

		dep[now]++;

		return;

	}

    int mid=(le+ri)>>1;

    if(loc<=mid)

	   add(lson,le,mid,loc);

    else

	   add(rson,mid+1,ri,loc);

}

int Find_fa(int edi,int now)

{

    int ff=Query(edi,1,n,now);

	//查询在这一版本里now这个集合所在的结点编号

    if(now==fa[ff])

	//如果这个结点编号属于now这个集合,则找到

	//如果不一样，则取出这个结点编号所指向的集合

	   return ff;

    return Find_fa(edi,fa[ff]);//接着去找

}

int main()

{

    n=read(),Q=read();

    Build(Edi[0],1,n);

    for(int i=1;i<=Q;++i)

    {

        int opt=read();

        if(opt==1)

        {

            Edi[i]=Edi[i-1];//先copy过来

            int x=read(),y=read();

            int fx=Find_fa(Edi[i],x);//取出结点编号

			int fy=Find_fa(Edi[i],y);//同上

            if(fa[fx]==fa[fy]) //如果是同一个集合

			   continue;

            if(dep[fx]>dep[fy])

			   swap(fx,fy);//按秩合并，把x往y合并(dep小的往大的合并)

            Update(Edi[i],Edi[i-1],1,n,fa[fx],fa[fy]);

            //因为有合并操作，所以要新开线段树出来了

			//注意后面两个参数是集合编号

            if(dep[fx]+1>dep[fy])

			   add(Edi[i],1,n,fa[fy]);

        }

        if(opt==2)

        {

            int kk=read();

            Edi[i]=Edi[kk];

        }

        if(opt==3)

        {

            Edi[i]=Edi[i-1];

            int x=read(),y=read();

            int fx=Find_fa(Edi[i],x),fy=Find_fa(Edi[i],y);

            if(fa[fx]==fa[fy])

			   puts("1");

            else

			    puts("0");

        }

    }

    return 0;

}

巴特西

可持久化并查集 by zky

最新文章

热门文章