n个集合 m个操作 操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^5 强制在线。
这两题一题都一样，另一题比较水，nm只有2*10^4,允许离线.....
做法很简单，把数组当作可持久化线段树那么维护，每个表示区间的节点都不存东西，每次只要新建log个节点。
我交水的那道过不去，绝望的时候我交了一发加强版居然A了，根据我多年的经验一定是有特殊数据的坑，特判了一波终于过了。
用了启发式合并之后复杂度nlog^2n
#include<iostream>
#include<cstdio>
#define MN 20000000
#define MM 200000
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int cnt=,n,m,last=,rt[MM+],cc;
struct data{
int x,size;
}s[MM*+];
struct TREE{
int l,r;
data *x;
}T[MN]; void build(int x,int l,int r)
{
if(l==r){T[x].x=&s[l];return;}
int mid=l+r>>;
build(T[x].l=(++cnt),l,mid);
build(T[x].r=(++cnt),mid+,r);
} data*get(int x,int k,int l=,int r=n)
{
if(l==r)return T[x].x;
int mid=l+r>>;
if(k<=mid) return get(T[x].l,k,l,mid);
else return get(T[x].r,k,mid+,r);
} data getfa(int x,int r)
{
data y=*get(r,x),ans=y;
if(!y.x)return (data){x,ans.size};
while(y.x) {ans=y;y=*get(r,y.x);}
return (data){ans.x,y.size};
} void ins(int x,int dep,int k)
{
int l=,r=n;int nx=rt[dep]=++cnt;
while(l<r)
{
int mid=l+r>>;
if(k<=mid)
{
T[nx].r=T[x].r;T[nx].l=++cnt;
nx=T[nx].l;x=T[x].l;r=mid;
}
else
{
T[nx].l=T[x].l;T[nx].r=++cnt;
nx=T[nx].r;x=T[x].r;l=mid+;
}
}
T[nx].x=&s[cc];
} int main()
{
cc=n=read();m=read();
for(int i=;i<=n;i++)s[i]=(data){,};
build(++cnt,,n);rt[]=;
for(int i=;i<=m;i++)
{
int a=read(),b=read()^last;
if(a==)
rt[i]=rt[b];
else
{
int c=read()^last;
if(a==) printf("%d\n",last=(getfa(b,rt[i-]).x==getfa(c,rt[i-]).x)),rt[i]=rt[i-];
else
{
data x=getfa(b,rt[i-]),y=getfa(c,rt[i-]);
if(x.x==y.x){rt[i]=rt[i-];continue;}
if(x.size>y.size)swap(x,y);
s[++cc]=(data){y.x,x.size};ins(rt[i-],i,x.x);
s[++cc]=(data){,x.size+y.size};ins(rt[i],i,y.x);
}
}
}
return ;
}