1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| #include<bits/stdc++.h> using namespace std; int n,m,key[300005]; int top,ch[300005][2],fa[300005],xsm[300005],que[300005],rev[300005]; void pushup(int x){xsm[x]=xsm[ch[x][0]]^xsm[ch[x][1]]^key[x];} void pushdown(int x) { if(rev[x]) { rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]^=1; swap(ch[x][0],ch[x][1]); } } bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} void rotate(int x) { int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1; if(!isroot(y)) { if(ch[z][0]==y) ch[z][0]=x; else ch[z][1]=x; } fa[x]=z; fa[y]=x; fa[ch[x][r]]=y; ch[y][l]=ch[x][r]; ch[x][r]=y; pushup(y); pushup(x); } void splay(int x) { top=0; que[++top]=x; for(int i=x;!isroot(i);i=fa[i]) que[++top]=fa[i]; for(int i=top;i;i--) pushdown(que[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if((ch[y][0]==x)^(ch[z][0]==y))rotate(x); else rotate(y); } rotate(x); } } void access(int x) { for(int t=0;x;t=x,x=fa[x]) { splay(x); ch[x][1]=t; pushup(x); } } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } int find(int x) { access(x); splay(x); while(ch[x][0]) x=ch[x][0]; return x; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void cut(int x,int y) { split(x,y); if(ch[y][0]==x&&ch[x][1]==0) ch[y][0]=fa[x]=0; } void link(int x,int y) { makeroot(x); fa[x]=y; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&key[i]),xsm[i]=key[i]; for(int i=1,opt,x,y;i<=m;i++) { scanf("%d%d%d",&opt,&x,&y); if(opt==0)split(x,y),printf("%d\n",xsm[y]); if(opt==1)if(find(x)!=find(y))link(x,y); if(opt==2)if(find(x)==find(y))cut(x,y); if(opt==3)access(x),splay(x),key[x]=y,pushup(x); } return 0; }
|