题目

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=200002,M=10000002;
int rt[N],cnt,L[M],R[M],dep[M],n,m,opt,x,rx,ry,las,v[M],y,i;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
void build(int &t,int l,int r){
	t=++cnt;
	if (l==r){
		v[t]=l;
		return;
	}
	build(L[t],l,mid);
	build(R[t],mid+1,r);
}
void modify(int l,int r,int x,int &y,int pos,int val){//复制后赋值 
	y=++cnt;
	if (l==r){
		v[y]=val;//fa[x]=y
		dep[y]=dep[x];
		return;
	}
	L[y]=L[x],R[y]=R[x];
	if (pos<=mid) modify(l,mid,L[x],L[y],pos,val);
	else modify(mid+1,r,R[x],R[y],pos,val);
}
int query(int t,int l,int r,int x){
	if (l==r) return t;
	if (x<=mid) return query(L[t],l,mid,x);
	return query(R[t],mid+1,r,x);
}
int find(int k,int x){
	int t=query(k,1,n,x);
	return x==v[t]?t:find(k,v[t]);//v[t]相当于fa[x],dep[t]相当于dep[x]
}
int main(){
	n=rd(),m=rd();
	build(rt[0],1,n);
	for (i=1;i<=m;i++){
		opt=rd(),x=rd()^las;
		if (opt&1){
			y=rd()^las,rt[i]=rt[i-1];
			rx=find(rt[i],x),ry=find(rt[i],y);
			if (opt==1){
				if (v[rx]==v[ry]) continue;
				if (dep[rx]>dep[ry]) swap(rx,ry);
				modify(1,n,rt[i-1],rt[i],v[rx],v[ry]);//fa[rx]=ry
				if (dep[rx]==dep[ry]) dep[query(rt[i],1,n,v[ry])]++;
			}else las=(v[rx]==v[ry]),putchar(las+48),puts("");
		}
		else rt[i]=rt[x];
	}
}