105 lines
1.8 KiB
C++
105 lines
1.8 KiB
C++
#include<cstdio>
|
|
#include<cstring>
|
|
#include<algorithm>
|
|
using namespace std;
|
|
const int maxn=1e5+5;
|
|
const int maxm=2e5+5;
|
|
const int maxmem=2*(maxn*2+20*maxm);
|
|
int n,m,op,a,b,t[maxn];
|
|
struct Array
|
|
{
|
|
int rtid,ncnt,rt[maxm],lc[maxmem],rc[maxmem],val[maxmem],p,upd;
|
|
void build(int &o,int L,int R)
|
|
{
|
|
o=++ncnt;
|
|
if(L==R) { val[o]=t[L]; return; }
|
|
int M=(L+R)>>1;
|
|
build(lc[o],L,M);
|
|
build(rc[o],M+1,R);
|
|
}
|
|
int modify(int o,int L,int R)
|
|
{
|
|
int no=++ncnt;
|
|
lc[no]=lc[o]; rc[no]=rc[o];
|
|
if(L==R) { val[no]=upd; return no; }
|
|
int M=(L+R)>>1;
|
|
if(p<=M) lc[no]=modify(lc[no],L,M);
|
|
else rc[no]=modify(rc[no],M+1,R);
|
|
return no;
|
|
}
|
|
int query(int o,int L,int R)
|
|
{
|
|
if(L==R) return val[o];
|
|
int M=(L+R)>>1;
|
|
if(p<=M) return query(lc[o],L,M);
|
|
else return query(rc[o],M+1,R);
|
|
}
|
|
void init()
|
|
{
|
|
rtid=ncnt=0;
|
|
build(rt[0],1,n);
|
|
}
|
|
inline void CopyFrom(int id)
|
|
{
|
|
rt[++rtid]=rt[id];
|
|
}
|
|
inline int get(int id,int p)
|
|
{
|
|
this->p=p;
|
|
return query(rt[rtid],1,n);
|
|
}
|
|
inline int set(int id,int p,int v)
|
|
{
|
|
this->p=p; upd=v;
|
|
rtid++;
|
|
rt[rtid]=modify(rt[rtid-1],1,n);
|
|
return v;
|
|
}
|
|
} fa,dep;
|
|
int ff(int id,int u)
|
|
{
|
|
int v;
|
|
while(v=fa.get(id,u),u!=v) u=v;
|
|
return u;
|
|
}
|
|
int main()
|
|
{
|
|
#ifdef local
|
|
freopen("pro.in","r",stdin);
|
|
#endif
|
|
scanf("%d%d",&n,&m);
|
|
dep.init();
|
|
for(int i=1;i<=n;i++) t[i]=i;
|
|
fa.init();
|
|
for(int i=1;i<=m;i++)
|
|
{
|
|
scanf("%d%d",&op,&a);
|
|
if(op==1)
|
|
{
|
|
scanf("%d",&b);
|
|
a=ff(i-1,a);
|
|
b=ff(i-1,b);
|
|
int ad=dep.get(i-1,a),bd=dep.get(i-1,b);
|
|
if(ad<bd) { swap(ad,bd); swap(a,b); }
|
|
fa.set(i-1,b,a);
|
|
if(ad==bd) dep.set(i-1,a,ad+1);
|
|
else dep.CopyFrom(i-1);
|
|
}
|
|
else if(op==2)
|
|
{
|
|
fa.CopyFrom(a);
|
|
dep.CopyFrom(a);
|
|
}
|
|
else
|
|
{
|
|
scanf("%d",&b);
|
|
a=ff(i-1,a);
|
|
b=ff(i-1,b);
|
|
puts(a==b?"1":"0");
|
|
fa.CopyFrom(i-1);
|
|
dep.CopyFrom(i-1);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|