题目大意：同3673 强制在线
同3673 仅仅只是慢了一些0.0
这道题仅仅写路径压缩比仅仅写启示式合并要快一点点 两个都写就慢的要死0.0
改代码RE的可能是内存不够
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200200
using namespace std;
struct Tree{
Tree *ls,*rs;
int num;
}*fa[M],mempool[M*60],*C=mempool;
int n,m,ans,now,version[M],tot;
inline Tree* New_Node(Tree *_,Tree *__,int ___)
{
C->ls=_;
C->rs=__;
C->num=___;
return C++;
}
Tree* Modify(Tree *p,int x,int y,int pos,int val)
{
int mid=x+y>>1;
if(x==y)
return New_Node(0x0,0x0,val);
if(pos<=mid)
return New_Node(Modify(p->ls,x,mid,pos,val),p->rs,0);
else
return New_Node(p->ls,Modify(p->rs,mid+1,y,pos,val),0);
}
int Access(Tree *p,int x,int y,int pos)
{
int mid=x+y>>1;
if(x==y)
return p->num;
if(pos<=mid)
return Access(p->ls,x,mid,pos);
else
return Access(p->rs,mid+1,y,pos);
}
int Find(int x)
{
int fx=Access(fa[now],1,n,x);
if(!fx)
return x;
int t=Find(fx);
Modify(fa[now],1,n,x,t);
return t;
}
inline void Unite(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx==fy)
return;
++tot;
fa[tot]=Modify(fa[now],1,n,fy,fx);
now=tot;
}
inline bool Query(int x,int y)
{
return Find(x)==Find(y);
}
int main()
{
int i,p,x,y;
cin>>n>>m;
fa[0]=New_Node(C,C,0);
for(i=1;i<=m;i++)
{
scanf("%d",&p);
switch(p)
{
case 1:scanf("%d%d",&x,&y),Unite(x^ans,y^ans);break;
case 2:scanf("%d",&x),now=version[x^ans];break;
case 3:scanf("%d%d",&x,&y),printf("%d\n",ans=Query(x^ans,y^ans));break;
}
version[i]=now;
}
}