bzoj1180: [CROATIAN2009]OTOCI

lct裸题QuQ
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 
  9 const int Maxn=30010;
 10 
 11 int ch[Maxn][2],w[Maxn],sum[Maxn],p[Maxn];
 12 bool flip[Maxn];
 13 
 14 bool isroot(int x) {
 15     return ch[p[x]][0]!=x && ch[p[x]][1]!=x;
 16 }
 17 
 18 #define l ch[x][0]
 19 #define r ch[x][1]
 20 
 21 void update(int x) {
 22     if(!x) return;
 23     sum[x] = w[x] + sum[l] + sum[r];
 24 }
 25 
 26 void down(int x) {
 27     if(!x) return;
 28     if(flip[x]) {
 29         swap(l,r);
 30         flip[l]^=1;
 31         flip[r]^=1;
 32         flip[x]^=1;
 33     }
 34 }
 35 
 36 #undef l
 37 #undef r
 38 
 39 void rotate(int x) {
 40     int y=p[x],z=p[y];
 41     if(!isroot(y)) ch[z][ch[z][1]==y] = x;
 42     int l=ch[y][1]==x,r=l^1;
 43     p[x]=z;
 44     p[y]=x;
 45     p[ch[x][r]]=y;
 46     
 47     ch[y][l]=ch[x][r];
 48     ch[x][r]=y;
 49     
 50     update(y);
 51     update(x);
 52 }
 53 
 54 void splay(int x) {
 55     static int stk[Maxn],top;
 56     stk[top=1]=x;
 57     for(int t=x;!isroot(t);t=p[t]) stk[++top]=p[t];
 58     while(top) down(stk[top--]);
 59     
 60     for(;!isroot(x);) {
 61         int y=p[x],z=p[y];
 62         if(!isroot(y)) {
 63             if( (ch[y][0]==x)^(ch[z][0]==y) )rotate(x);
 64             rotate(y);
 65         }
 66         rotate(x);
 67     }
 68 }
 69 
 70 void access(int x) {
 71     for(int t=0;x;x=p[t=x]) {
 72         splay(x);
 73         ch[x][1]=t;
 74         update(x);
 75     }
 76 }
 77 
 78 int getroot(int x) {
 79     for(access(x),splay(x);ch[x][0];x=ch[x][0]);
 80     return x;
 81 }
 82 
 83 void newroot(int x) {
 84     access(x);
 85     splay(x);
 86     flip[x]^=1;
 87 }
 88 
 89 void Link(int x,int y) {
 90     newroot(x);
 91     p[x]=y;
 92 }
 93 
 94 int n,m;
 95 
 96 void init() {
 97     scanf("%d",&n);
 98     for(int i=1;i<=n;i++) {
 99         scanf("%d",w+i);
100         sum[i]=w[i];
101     }
102 }
103 
104 void work() {
105     char opt[100];
106     int x,y;
107     for(scanf("%d",&m);m--;) {
108         scanf("%s%d%d",opt,&x,&y);
109         if(opt[0]=='b') {
110             if(getroot(x)==getroot(y)) puts("no");
111             else Link(x,y),puts("yes");
112         }else if(opt[0]=='p') {
113             access(x);
114             splay(x);
115             w[x]=y;
116             update(x);
117         }else /*if(opt[0]==e)*/ {
118             if(getroot(x)!=getroot(y)) puts("impossible");
119             else {
120                 newroot(x);
121                 access(y);
122                 splay(y);
123                 printf("%d
",sum[y]);
124             }
125         }
126     }
127 }
128 
129 int main() {
130 #ifdef DEBUG
131     freopen("in.txt","r",stdin);
132 //    freopen("out.txt","w",stdout);
133 #endif
134     
135     init();
136     work();
137     
138     return 0;
139 }