记录编号	250634	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.653 s
提交时间	2016-04-15 16:37:42	内存使用	152.94 MiB

#include<cstdio>
#include<iostream>
 
#define maxn  400100
#define lson tr[rt].l
#define rson tr[rt].r
 
using namespace std;
 
int n,m,i,f[maxn*20],rot[maxn*20],num,deep[maxn*20];
 
struct Tree{
    int l,r;
}tr[maxn*20];
 
void build(int &rt,int l,int r){
    rt=++num;
    if(l==r){
        f[rt]=l;
        return;
    }
    f[rt]=1;
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
 
void Modify(int pre,int &rt,int pos,int fa,int l,int r){
    rt=++num;
    tr[rt]=tr[pre];
    if(l==r){
        f[rt]=fa;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) Modify(tr[pre].l,lson,pos,fa,l,mid);
    else Modify(tr[pre].r,rson,pos,fa,mid+1,r);
    return;
}
 
int Query(int pos,int l,int r,int rt)
{
    if(l==r) return rt;
    int mid=(l+r)>>1;
    if(pos<=mid) return Query(pos,l,mid,lson);
    else return Query(pos,mid+1,r,rson);
}
 
int getf(int x){
    int t=Query(x,1,n,rot[i-1]);
    if(f[t]==x) return t;
    return getf(f[t]);
}
 
void add(int pos,int rt,int l,int r)
{
    if(l==r){
        deep[rt]++;return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) add(pos,lson,l,mid);
    else add(pos,rson,mid+1,r);
    return ;
}
 
int main()
{
	freopen("bzoj_3974.in","r",stdin);
	freopen("bzoj_3974.out","w",stdout);
    scanf("%d%d",&n,&m);
    build(rot[0],1,n);
    int lastans=0;
    for(i=1;i<=m;i++){
        int cmd;scanf("%d",&cmd);
        if(cmd==1){
            int x,y;
            scanf("%d%d",&x,&y);
            x^=lastans,y^=lastans;
            int A=getf(x),B=getf(y);
            if(f[A]==f[B]){
                rot[i]=rot[i-1];
                continue;
            }
            if(deep[A]>deep[B]) swap(A,B);
            Modify(rot[i-1],rot[i],f[A],f[B],1,n);
            if(deep[A]==deep[B]) add(f[B],rot[i],1,n);
        }
        if(cmd==2){
            int k;scanf("%d",&k);
            k^=lastans;
            rot[i]=rot[k];
        }
        if(cmd==3){
            int x,y;
            rot[i]=rot[i-1];
            scanf("%d%d",&x,&y);
            x^=lastans,y^=lastans;
            if(getf(x)==getf(y)){
                printf("1\n");
                lastans=1;
            }else{
                lastans=0;
                printf("0\n");
            }
        }
    }
}