记录编号	432796	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.466 s
提交时间	2017-08-03 20:09:49	内存使用	62.09 MiB

#include <stdio.h>
#include <cmath>
#include <cstring>
const int MAXN = 200005;
int n,m,deep[MAXN*20],cnt,fa[MAXN*20],Ans,root[MAXN];


template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
struct node{
    int l,r;
}tree[MAXN*20];

#define l(x) tree[x].l
#define r(x) tree[x].r

inline void build(int &o,int l,int r){
    o=++cnt;
    if(l==r){fa[o]=l;return;}
    int m=l+r>>1;
    build(l(o),l,m);
    build(r(o),m+1,r);
}

inline void insert(int &o,int old,int l,int r,int pos,int val){
    o=++cnt;
    tree[o]=tree[old];
    if(l==r){fa[o]=val;deep[o]=deep[old];return;}
    int m = l+r>>1;
    if(pos<=m)insert(l(o),l(old),l,m,pos,val);
    else insert(r(o),r(old),m+1,r,pos,val);
    return;
}

inline int Query(int o,int l,int r,int pos){
    if(l==r)return o;
    int m=l+r>>1;
    if(pos<=m)return Query(l(o),l,m,pos);
    else return Query(r(o),m+1,r,pos);
}

inline void Update(int o,int l,int r,int pos){
    if(l==r){++deep[o];return;}
    int m=l+r>>1;
    if(pos<=m)Update(l(o),l,m,pos);
    else Update(r(o),m+1,r,pos);
}

int find(int id,int x){
    int f = Query(root[id],1,n,x);
    if(fa[f]==x)return f;
    return find(id,fa[f]);
}

int main(){
    freopen("bzoj_3974.in","r",stdin);
    freopen("bzoj_3974.out","w",stdout);
    n=read<int>();m=read<int>();
    build(root[0],1,n);
    for(int i=1;i<=m;i++){
        int op = read<int>();
        if(op==1){
            root[i]=root[i-1];
            int u=read<int>()^Ans,v=read<int>()^Ans;
            u=find(i,u);v=find(i,v);
            if(fa[u]==fa[v]){continue;}
            if(deep[fa[u]]<deep[fa[v]])swap(u,v);
            insert(root[i],root[i-1],1,n,fa[v],fa[u]);
            if(deep[u]==deep[v])Update(root[i],1,n,fa[u]);
        }
        if(op==2){  
            int k=read<int>()^Ans;
            root[i]=root[k];
        }
        if(op==3){
            root[i]=root[i-1];
            int u=read<int>()^Ans,v=read<int>()^Ans;
            u=find(i,u);v=find(i,v);
            Ans=(u==v);
            printf("%d\n",Ans);
        }
    }
}