可持久化并查集的模板题……
做法好像很多，可以标号法，可以森林法。
本来有O(mloglogn)的神算法(按秩合并+倍增)，然而我这种鶸渣就只会写O(mlog2n)的民科算法……再加上人傻常数大如狗，速度简直虚死……
言归正传，鉴于标号法用的不多，这里用的是森林法。又由于并查集的路径压缩只能均摊logn，如果可持久化一下就废了。所以路径压缩大可不写，正好偷偷懒。
当然，路径压缩都省了，那按秩合并就不能不写了(要不然为啥要出加强版……)。然而我太鶸，不会写按秩合并，一向都是用按大小合并代替的……不过效果还不错，复杂度好像也是个log。
可持久化数组好像有用vector记录修改的神写法，然而我这种鶸渣只会写可持久化线段树……本来就是nlogn了，再乘上一个logn，运行时间实在感人……
总之，写的是可持久化线段树+按秩合并+暴力找父亲(不过貌似大家都是写的按秩合并暴力？然而明明同样O(mlog2n)的算法我就是最慢的那个……)。代码丑，不愿看……就算了……
/**************************************************************
Problem: 3674
User: hzoier
Language: C++
Result: Accepted
Time:1636 ms
Memory:201612 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int findroot(int);
void mergeset(int,int);
void build(int,int,int&);
void modify(int,int,int&);
void query(int,int,int);
int copy(int);
int lc[maxn<<],rc[maxn<<],a[maxn<<],b[maxn<<],root[maxn],cnt=;
int n,m,d,x,y,k,prt,size,now,ans=;
int main(){
scanf("%d%d",&n,&m);
build(,n,root[]);
for(now=;now<=m;now++){
scanf("%d",&d);
if(d==){
scanf("%d%d",&x,&y);
x^=ans;y^=ans;
root[now]=copy(root[now-]);
mergeset(x,y);
}
else if(d==){
scanf("%d%d",&x,&y);
x^=ans;y^=ans;
root[now]=copy(root[now-]);
printf("%d\n",ans=(int)(findroot(x)==findroot(y)));
}
else{
scanf("%d",&x);
x^=ans;
root[now]=copy(root[x]);
}
}
return ;
}
int findroot(int x){
for(;;){
k=x;
query(,n,root[now]);
if(prt==x)return x;
x=prt;
}
return x;
}
void mergeset(int x,int y){
x=findroot(x);y=findroot(y);
if(x==y)return;
k=x;
query(,n,root[now]);
int sx=size;
k=y;
query(,n,root[now]);
if(sx>size)swap(x,y);
sx+=size;
size=;
k=x;
prt=y;
modify(,n,root[now]);
k=y;
size=sx;
modify(,n,root[now]);
}
void build(int l,int r,int &rt){
rt=++cnt;
if(l==r){
a[rt]=l;
b[rt]=;
return;
}
int mid=(l+r)>>;
build(l,mid,lc[rt]);
build(mid+,r,rc[rt]);
}
void modify(int l,int r,int &rt){
rt=copy(rt);
if(l==r){
if(prt)a[rt]=prt;
if(size)b[rt]=size;
return;
}
int mid=(l+r)>>;
if(k<=mid)modify(l,mid,lc[rt]);
else modify(mid+,r,rc[rt]);
}
void query(int l,int r,int rt){
if(l==r){
prt=a[rt];
size=b[rt];
return;
}
int mid=(l+r)>>;
if(k<=mid)query(l,mid,lc[rt]);
else query(mid+,r,rc[rt]);
}
int copy(int rt){
int x=++cnt;
lc[x]=lc[rt];
rc[x]=rc[rt];
a[x]=a[rt];
b[x]=b[rt];
return x;
}
尽头和开端，总有一个在等你。