本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
Input
Output
Sample Input
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
Sample Output
1
0
1
0
1
正解：启发式合并+线段树
解题报告：
这道题是启发式合并的练手好题…
为了满足题目要求，我需要对于每个历史版本维护fa，想想就会发现这个其实和主席树是有相通之处的，都是每个节点维护了一棵线段树，然后每次修改只会修改到一条链，这道题也是一样的。
那么我对于每个节点维护一棵线段树，其中只有叶子节点里面存储了关键信息，其余节点其实没有任何信息的存储。
我记录一下每个历史版本的线段树的根节点，可以把当前状态直接指向历史版本中的根，所以可以做到O(1)撤销。
查询的话直接插在当前状态下是否是同一个祖先即可，注意不能路径压缩。还有就是讲一下按秩合并的相关问题，首先秩表示的是以这个元素为祖先的所有元素中的最大深度。
很明显，并查集的复杂度直接和查询的最大深度有关，所以我应该以最大深度作为合并时的评判标准。
然后只有在合并之前两棵子树秩相同的时候，才需要修改新树的秩，否则由于小的那个的秩<大的那个的秩，最大深度不会超过大的那个。
这是一点细节上的说明。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
const int MAXM = 5000011;
int n,m,root[MAXN],cnt,ans;
struct node{ int ls,rs,deep,fa; }a[MAXM];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void build(int &k,int l,int r){
k=++cnt; if(l==r) { a[k].deep=1; a[k].fa=l; return ; }
int mid=(l+r)>>1; build(a[k].ls,l,mid); build(a[k].rs,mid+1,r);
}
inline int query(int rt,int l,int r,int val){
int u=rt,mid;
while(1) {
if(l==r) return u; mid=(l+r)>>1;
if(val<=mid) r=mid,u=a[u].ls;
else l=mid+1,u=a[u].rs;
}
}
inline void add(int &k,int from,int l,int r,int val){
k=++cnt; if(l==r) { a[k].fa=val; a[k].deep=a[from].deep+1;/*!!!*/ return ; }
a[k].ls=a[from].ls; a[k].rs=a[from].rs;
int mid=(l+r)>>1;
if(val<=mid) add(a[k].ls,a[from].ls,l,mid,val);
else add(a[k].rs,a[from].rs,mid+1,r,val);
}
inline void update(int &k,int from,int l,int r,int A,int Fa){
k=++cnt; if(l==r) { a[k].fa=Fa; a[k].deep=a[from].deep;/*!!!*/ return ; }
a[k].ls=a[from].ls; a[k].rs=a[from].rs;
int mid=(l+r)>>1;
if(A<=mid) update(a[k].ls,a[from].ls,l,mid,A,Fa);
else update(a[k].rs,a[from].rs,mid+1,r,A,Fa);
}
inline int find(int rt,int x){//在rt为根的线段树中查找x所在的集合的祖先
int Node=query(rt,1,n,x);//先在线段树中找到x所在的叶子节点对应的线段树节点编号
if(a[Node].fa==x) return Node;
return find(rt,a[Node].fa);
}
inline void work(){
n=getint(); m=getint(); ans=0;
build(root[0],1,n); int x,y,r1,r2,ljh;
for(int i=1;i<=m;i++) {
ljh=getint(); root[i]=root[i-1];
if(ljh==1) {
x=getint(); y=getint();
r1=find(root[i],x); r2=find(root[i],y); if(a[r1].fa==a[r2].fa) continue;//!!!
if(a[r1].deep>a[r2].deep) swap(r1,r2);
update(root[i],root[i-1],1,n,a[r1].fa,a[r2].fa);
if(a[r1].deep==a[r2].deep) add(root[i],root[i],1,n,a[r2].fa);//考虑最大深度相等时，合并之后秩会+1
}
else if(ljh==2) { x=getint(); root[i]=root[x]; }
else {
x=getint(); y=getint();
r1=find(root[i],x); r2=find(root[i],y);
if(r1==r2) { puts("1"); ans=1; } else { puts("0"); ans=0; }
}
}
}
int main()
{
work();
return 0;
}