记录编号	488959	评测结果	AAWWWWAAWA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	50
用户昵称	_WA自动机	是否通过	未通过
代码语言	C++	运行时间	0.299 s
提交时间	2018-02-25 23:37:37	内存使用	94.86 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+1000;
struct node
{
    int ls,rs,sum;
}patree[maxn*20],wtree[maxn*20];
int rootpa[maxn],rootw[maxn],psum,n,wsum;
namespace IO
{
    char buf[1<<20|1],*fs,*ft;
    inline char gc()
    {
        if (fs==ft)
        {
            ft=(fs=buf)+fread(buf,1,1<<20|1,stdin);
            if (fs==ft) return -1;
        }
        return *fs++;
    }
    #ifdef COGS
    #define gc() getchar()
    #endif // COGS
    inline int read()
    {
        char ch;
        while (!isdigit(ch=gc()));
        int x=ch-48;
        while (isdigit(ch=gc()))
            x=x*10+ch-48;
        return x;
    }
}using namespace IO;
void buildpa(int l,int r,int &o)
{
    o=++psum;
    if (l==r) {patree[o].sum=l;return;}
    int m=(l+r)>>1;
    buildpa(l,m,patree[o].ls);
    buildpa(m+1,r,patree[o].rs);
}
void buildw(int l,int r,int &o)
{
    o=++wsum;
    if (l==r) {wtree[o].sum=0;return;}
    int m=(l+r)>>1;
    buildw(l,m,wtree[o].ls);
    buildw(m+1,r,wtree[o].rs);
}
void updatepa(int v,int p,int &now,int pre,int l,int r)
{
    now=++psum;
    patree[now]=patree[pre];
    if (l==r) {patree[now].sum=v;return;}
    int m=(l+r)>>1;
    if (p<=m) updatepa(v,p,patree[now].ls,patree[pre].ls,l,m);
    else updatepa(v,p,patree[now].rs,patree[pre].rs,m+1,r);
}
void updatew(int v,int p,int& now,int pre,int l,int r)
{
    now=++wsum;
    wtree[now]=wtree[pre];
    if (l==r) {wtree[now].sum+=v;return;}
    int m=(l+r)>>1;
    if (p<=m) updatew(v,p,wtree[now].ls,wtree[pre].ls,l,m);
    else updatew(v,p,wtree[now].rs,wtree[pre].rs,m+1,r);
}
int querypa(int p,int o,int l,int r)
{
    if (l==r) return patree[o].sum;
    int m=(l+r)>>1;
    if (p<=m) return querypa(p,patree[o].ls,l,m);
    else return querypa(p,patree[o].rs,m+1,r);
}
int queryw(int p,int o,int l,int r)
{
    if (l==r) return wtree[o].sum;
    int m=(l+r)>>1;
    if (p<=m) return queryw(p,wtree[o].ls,l,m);
    return queryw(p,wtree[o].rs,m+1,r);

}
int find(int u,int i)
{
    int fa=querypa(u,rootpa[i],1,n);
    return u==fa?u:find(fa,i);
}
void merge(int u,int v,int i)
{
    int x=find(u,i-1),y=find(v,i-1);
    int w1=queryw(x,rootw[i-1],1,n),w2=queryw(y,rootw[i-1],1,n);
    if (w1<w2) updatepa(y,x,rootpa[i],rootpa[i-1],1,n);
    else
    {
        updatepa(x,y,rootpa[i],rootpa[i-1],1,n);
        if (w1==w2) updatew(1,x,rootw[i],rootw[i-1],1,n);
    }
}
int query(int u,int v,int i)
{
    int x=find(u,i),y=find(v,i);
    return x==y;
}
int main()
{
    freopen("bzoj_3974.in","r",stdin);
    freopen("bzoj_3974.out","w",stdout);
    int m,opt,a,b,k;
    n=read();m=read();
    buildpa(1,n,rootpa[0]);
    buildw(1,n,rootw[0]);
    int la=0;
    for (register int i=1;i<=m;++i)
    {
        opt=read();
        rootpa[i]=rootpa[i-1];rootw[i]=rootw[i-1];
        if (opt==1)
        {
            a=read()^la;b=read()^la;
            merge(a,b,i);
        }
        else if (opt==2)
        {
            k=read()^la;
            rootpa[i]=rootpa[k];
            rootw[i]=rootw[k];
        }
        else
        {
            a=read()^la;b=read()^la;
            printf("%d\n",la=query(a,b,i));
        }
    }
}