文件详细信息

下载本文件

本文件的大小为 2442 字节。

#include<cstdio>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt;
		if(a==0)pc('0');
		cnt=0;
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
void swap(int&a,int&b){
	int temp=a;
	a=b;
	b=temp;
}
const int maxn=100005,maxm=200005,maxlogn=25;
int n,m,tot;
struct Seg{
	int fa,sz,l,r;
}t[(maxn<<2)+maxm*maxlogn];
int rt[maxm];
void build(int&u,int l,int r){
	u=++tot;
	if(l==r){
		t[u].fa=l;
		t[u].sz=1;
		return;
	}
	int m=(l+r)>>1;
	build(t[u].l,l,m);
	build(t[u].r,m+1,r);
}
int query(int u,int l,int r,int x){
	if(l==r)return u;
	int m=(l+r)>>1;
	if(x<=m)return query(t[u].l,l,m,x);
	else return query(t[u].r,m+1,r,x);
}
int find(int rt,int pos){
	int tmp=query(rt,1,n,pos);
	return t[tmp].fa==pos?tmp:find(rt,t[tmp].fa);
}
void merge(int lst,int&rt,int l,int r,int x,int fa){
	rt=++tot;
	t[rt].l=t[lst].l,t[rt].r=t[lst].r;
	if(l==r){
		t[rt].fa=fa;
		t[rt].sz=t[lst].sz;
		return;
	}
	int m=(l+r)>>1;
	if(x<=m)merge(t[lst].l,t[rt].l,l,m,x,fa);
	else merge(t[lst].r,t[rt].r,m+1,r,x,fa);
}
void modify(int u,int l,int r,int x){
	if(l==r){
		t[u].sz++;
		return;
	}
	int m=(l+r)>>1;
	if(x<=m)modify(t[u].l,l,m,x);
	else modify(t[u].r,m+1,r,x);
}
int main(){
	read(n),read(m);
	build(rt[0],1,n);
	int opt,a,b,k;
	for(int i=1;i<=m;i++){
		read(opt);
		if(opt==1){
			read(a),read(b);
			rt[i]=rt[i-1];
			a=find(rt[i],a),b=find(rt[i],b);
			if(t[a].fa!=t[b].fa){
				if(t[a].sz>t[b].sz)swap(a,b);
				merge(rt[i-1],rt[i],1,n,t[a].fa,t[b].fa);
				if(t[a].sz==t[b].sz)modify(rt[i],1,n,t[b].fa);
			}
		}else if(opt==2){
			read(k);
			rt[i]=rt[k];
		}else{
			read(a),read(b);
			rt[i]=rt[i-1];
			a=find(rt[i],a),b=find(rt[i],b);
			pc(t[a].fa==t[b].fa?'1':'0'),pc('\n');
		}
	}
	return 0;
}