本文共 5475 字，大约阅读时间需要 18 分钟。

妈个鸡。。。。没加强的没有要求在线。。。

我日了狗了  查了半天错。。。。

反正就是用可持久化线段树维护一个可持久化数组具体看代码

/**************************************************************    Problem: 3674    User: liutian    Language: C++    Result: Accepted    Time:1424 ms    Memory:180884 kb****************************************************************/ #include
   
    #include
    
     #include
     
      using namespace std; char c;inline void read(int &a){a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();} struct Node{Node *lc,*rc;int data;}*Tree[2000001];Node a  [10000001];Node* st[10000001];int con_d;inline void begin(){for(con_d=0;con_d<=10000000;con_d++)st[con_d]=&a[con_d];con_d--;}inline Node *New_Node(){st[con_d]->lc=NULL;st[con_d]->rc=NULL;return st[con_d--];}int timeee;int n;inline int f(Node *a,int l,int r,int pl){    if(l^r)       {        int mid=(l+r)>>1;        if(mid
      
       rc,mid+1,r,pl);        return f(a->lc,l,mid,pl);       }    return a->data;}Node *change(Node *a,int l,int r,int pl,int delta){    if(l^r)    {    int mid=(l+r)>>1;        Node *tp=New_Node();        *tp=*a;        if(mid
       
        rc=change(tp->rc,mid+1,r,pl,delta);        else tp->lc=change(tp->lc,l,mid,pl,delta);       return tp;    }    Node *tp=New_Node();    tp->data=delta;return tp;}#define f(x) f(Tree[timeee],1,n,x) int find(int x){    int res,t;    t=f(x);    if((res=f(t))!=t)       Tree[timeee]=change(Tree[timeee],1,n,x,res=find(t));    return res;} Node* build_start(int l,int r){    Node*a=New_Node();   if(l^r)     {    int mid=(l+r)>>1;    a->lc=build_start(l,mid);    a->rc=build_start(mid+1,r);    return a;   }   a->data=l;   return a;} int main(){    int m,lastans=0;    read(n),read(m);begin();    Tree[0]=build_start(1,n);    int flag,j,k,f1,f2;      for(int i=1;i<=m;i++)       {            read(flag);           if(flag==1)               {                timeee=i;                Tree[i]=Tree[i-1];                read(j),read(k);                j^=lastans,k^=lastans;                f1=find(j);f2=find(k);                                 if(f1!=f2)Tree[i]=change(Tree[i],1,n,f1,f2);               }            if(flag==2)                {                    read(j);                    j^=lastans;                    timeee=i;                    Tree[i]=Tree[j];                }            if(flag==3)                {                    timeee=i;                    read(j),read(k);                    Tree[i]=Tree[i-1];                    j^=lastans;k^=lastans;                    f1=find(j),f2=find(k);                    if(f1==f2)                        putchar('1'),putchar('\n'),lastans=1;                    else                         putchar('0'),putchar('\n'),lastans=0;                }       }    return 0;}
       
      
     
    
   

/**************************************************************    Problem: 3673    User: liutian    Language: C++    Result: Accepted    Time:144 ms    Memory:64552 kb****************************************************************/ #include
    
     #include
     
      #include
      
       using namespace std; char c;inline void read(int &a){a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();} struct Node{Node *lc,*rc;int data;}*Tree[200001];Node a  [4000001];Node* st[4000001];int con_d;inline void begin(){for(con_d=0;con_d<=4000000;con_d++)st[con_d]=&a[con_d];con_d--;}inline Node *New_Node(){st[con_d]->lc=NULL;st[con_d]->rc=NULL;return st[con_d--];}int timeee;int n;inline int f(Node *a,int l,int r,int pl){    if(l^r)       {        int mid=(l+r)>>1;        if(mid
       
        rc,mid+1,r,pl);        return f(a->lc,l,mid,pl);       }    return a->data;}Node *change(Node *a,int l,int r,int pl,int delta){    if(l^r)    {    int mid=(l+r)>>1;        Node *tp=New_Node();        *tp=*a;        if(mid
        
         rc=change(tp->rc,mid+1,r,pl,delta);        else tp->lc=change(tp->lc,l,mid,pl,delta);       return tp;    }    Node *tp=New_Node();    tp->data=delta;return tp;}#define f(x) f(Tree[timeee],1,n,x) int find(int x){    int res,t;    t=f(x);    if((res=f(t))!=t)       Tree[timeee]=change(Tree[timeee],1,n,x,res=find(t));    return res;} Node* build_start(int l,int r){    Node*a=New_Node();   if(l^r)     {    int mid=(l+r)>>1;    a->lc=build_start(l,mid);    a->rc=build_start(mid+1,r);    return a;   }   a->data=l;   return a;} int main(){    int m,lastans=0;    read(n),read(m);begin();    Tree[0]=build_start(1,n);    int flag,j,k,f1,f2;      for(int i=1;i<=m;i++)       {            read(flag);           if(flag==1)               {                timeee=i;                Tree[i]=Tree[i-1];                read(j),read(k);//              j^=lastans,k^=lastans;                f1=find(j);f2=find(k);                                 if(f1!=f2)Tree[i]=change(Tree[i],1,n,f1,f2);               }            if(flag==2)                {                    read(j);//                  j^=lastans;                    timeee=i;                    Tree[i]=Tree[j];                }            if(flag==3)                {                    timeee=i;                    read(j),read(k);                    Tree[i]=Tree[i-1];//                  j^=lastans;k^=lastans;                    f1=find(j),f2=find(k);                    if(f1==f2)                        putchar('1'),putchar('\n'),lastans=1;                    else                         putchar('0'),putchar('\n'),lastans=0;                }       }    return 0;}