RT，开了O2还有一个点 1.20s

#include<bits/stdc++.h>
using namespace std;
const int maxn=3400005;
int n,m;
int tot,rt[maxn],lc[maxn],rc[maxn];
int f[maxn],dep[maxn];
int kx,ky,ans=0;
void build(int& rt,int l,int r)
{
	rt=++tot;
	if(l==r)
	{
		f[rt]=l;
		return;	
	}
	int mid=(l+r)>>1;
	build(lc[rt],l,mid);
	build(rc[rt],mid+1,r);
}
int query(int rt,int l,int r,int k)
{
	int mid=(l+r)>>1;
	if(l==r) return rt;
	if(k<=mid) return query(lc[rt],l,mid,k);
	return query(rc[rt],mid+1,r,k);
}
void update(int rt,int l,int r,int k)
{
	if(l==r)
	{
		dep[rt]++;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid) update(lc[rt],l,mid,k);
	else update(rc[rt],mid+1,r,k);
}
void merge(int rt1,int& rt2,int l,int r,int k,int fa)
{
	rt2=++tot;
	lc[rt2]=lc[rt1];
	rc[rt2]=rc[rt1];
	if(l==r)
	{
		f[rt2]=fa;
		dep[rt2]=dep[rt1];
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid) merge(lc[rt1],lc[rt2],l,mid,k,fa);
	else merge(rc[rt1],rc[rt2],mid+1,r,k,fa);
}
int find(int rt,int k)
{
	
	int tmp=query(rt,1,n,k);
//	printf("FIND %d %d %d %d\n",rt,k,tmp,f[tmp]);
	if(f[tmp]==k) return tmp;
//	printf("***");
	return find(rt,f[tmp]);
}

void solve_merge(int k,int x,int y)
{
	rt[k]=rt[k-1];
	kx=find(rt[k],x);
	ky=find(rt[k],y);
	if(f[kx]!=f[ky])
	{
		if(dep[kx]>dep[ky]) swap(kx,ky);
		merge(rt[k-1],rt[k],1,n,f[kx],f[ky]);
		if(dep[kx]==dep[ky]) update(rt[k],1,n,f[kx]);
	}
}
void solve_find(int k,int x,int y)
{
	rt[k]=rt[k-1];
	kx=find(rt[k],x);
	ky=find(rt[k],y);
	if(f[kx]==f[ky]) printf("%d\n",ans=1);
	else printf("%d\n",ans=0);
}
int main()
{
	scanf("%d%d",&n,&m);
	build(rt[0],1,n);
	int ta,tb,tc;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&ta);
		if(ta==1)
		{
			scanf("%d%d",&tb,&tc);
//			tb^=ans;
//		tc^=ans;
//			printf("%d %d\n",tb ,tc);
			solve_merge(i,tb,tc);
		}
		if(ta==2)
		{
			scanf("%d",&tb);
//			tb^=ans;
			rt[i]=rt[tb];
		}
		if(ta==3)
		{
			scanf("%d%d",&tb,&tc);
//			tb^=ans;
//			tc^=ans;
			solve_find(i,tb,tc);
		}
	}
	return 0;
}