P3402 【模板】可持久化并查集

传送门
//minamoto

#include<bits/stdc++.h>

using namespace std;

#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

char buf[1<<21],*p1=buf,*p2=buf;

int read(){

    int res,f=1;char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=2e5+5;

int n,m,fa[N<<5],dep[N<<5],L[N<<5],R[N<<5],rt[N],cnt;

void build(int &p,int l,int r){

	p=++cnt;if(l==r)return (void)(fa[p]=l);

	int mid=(l+r)>>1;

	build(L[p],l,mid),build(R[p],mid+1,r);

}

void upd(int &p,int las,int l,int r,int x,int v){

	p=++cnt;if(l==r)return (void)(fa[p]=v,dep[p]=dep[las]);

	L[p]=L[las],R[p]=R[las];int mid=(l+r)>>1;

	x<=mid?upd(L[p],L[las],l,mid,x,v):upd(R[p],R[las],mid+1,r,x,v);

}

int query(int p,int l,int r,int x){

	if(l==r)return p;int mid=(l+r)>>1;

	return x<=mid?query(L[p],l,mid,x):query(R[p],mid+1,r,x);

}

void add(int p,int l,int r,int x){

	if(l==r)return (void)(++dep[p]);

	int mid=(l+r)>>1;

	x<=mid?add(L[p],l,mid,x):add(R[p],mid+1,r,x);

}

int find(int id,int x){

	int fat=query(id,1,n,x);

	return x==fa[fat]?fat:find(id,fa[fat]);

}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),build(rt[0],1,n);

	for(int i=1;i<=m;++i){

		int op=read();

		switch(op){

			case 1:{

				int x=read(),y=read();rt[i]=rt[i-1];

				int fatx=find(rt[i],x),faty=find(rt[i],y);

				if(fatx==faty)continue;if(dep[fatx]>dep[faty])swap(fatx,faty);

				upd(rt[i],rt[i-1],1,n,fa[fatx],fa[faty]);

				if(dep[fatx]==dep[faty])add(rt[i],1,n,fa[faty]);

				break;

			}

			case 2:{

				int k=read();rt[i]=rt[k];

				break;

			}

			case 3:{

				int x=read(),y=read();rt[i]=rt[i-1];

				int fatx=find(rt[i],x),faty=find(rt[i],y);

				puts(fatx==faty?"1":"0");

				break;

			}

		}

	}

	return 0;

}
巴特西

P3402 【模板】可持久化并查集

最新文章

热门文章
