HDU 3487 Play with Chain

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 300010;
  4 struct SplayTree {
  5     int val[maxn],fa[maxn],ch[maxn][2];
  6     int flip[maxn],sz[maxn],tot,root;
  7     bool flag;
  8     inline void pushdown(int x) {
  9         if(flip[x]) {
 10             flip[ch[x][0]] ^= 1;
 11             flip[ch[x][1]] ^= 1;
 12             swap(ch[x][0],ch[x][1]);
 13             flip[x] = 0;
 14         }
 15     }
 16     inline void pushup(int x) {
 17         sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]];
 18     }
 19     void newnode(int &x,int key,int f) {
 20         x = ++tot;
 21         val[x] = key;
 22         fa[x] = f;
 23         sz[x] = 1;
 24         flip[x] = ch[x][0] = ch[x][1] = 0;
 25     }
 26     void rotate(int x,int kd) {
 27         int y = fa[x];
 28         pushdown(y);
 29         pushdown(x);
 30         ch[y][kd^1] = ch[x][kd];
 31         fa[ch[x][kd]] = y;
 32         fa[x] = fa[y];
 33         ch[x][kd] = y;
 34         fa[y] = x;
 35         if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x;
 36         pushup(y);
 37     }
 38     void splay(int x,int goal) {
 39         pushdown(x);
 40         while(fa[x] != goal) {
 41             pushdown(fa[fa[x]]);
 42             pushdown(fa[x]);
 43             pushdown(x);
 44             if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]);
 45             else {
 46                 int y = fa[x],z = fa[y],s = (y == ch[z][0]);
 47                 if(x == ch[y][s]) {
 48                     rotate(x,s^1);
 49                     rotate(x,s);
 50                 } else {
 51                     rotate(y,s);
 52                     rotate(x,s);
 53                 }
 54             }
 55         }
 56         pushup(x);
 57         if(!goal) root = x;
 58     }
 59     void select(int k,int goal){
 60         int x = root;
 61         pushdown(x);
 62         while(sz[ch[x][0]] + 1 != k){
 63             if(k < sz[ch[x][0]] + 1) x = ch[x][0];
 64             else{
 65                 k -= sz[ch[x][0]] + 1;
 66                 x = ch[x][1];
 67             }
 68             pushdown(x);
 69         }
 70         splay(x,goal);
 71     }
 72     void build(int &x,int L,int R,int f){
 73         if(L > R) return;
 74         int mid = (L + R)>>1;
 75         newnode(x,mid,f);
 76         build(ch[x][0],L,mid-1,x);
 77         build(ch[x][1],mid + 1,R,x);
 78         pushup(x);
 79     }
 80     void init(int n){
 81         sz[0] = tot = root = 0;
 82         flip[0] = ch[0][0] = ch[0][1] = 0;
 83         val[0] = fa[0] = 0;
 84         newnode(root,-1,0);
 85         newnode(ch[root][1],-1,root);
 86         sz[root] = 2;
 87         build(ch[ch[root][1]][0],1,n,ch[root][1]);
 88     }
 89     void OUT(int x){
 90         if(!x) return;
 91         pushdown(x);
 92         OUT(ch[x][0]);
 93         if(~val[x]){
 94             if(flag) putchar(‘ ‘);
 95             printf("%d",val[x]);
 96             flag = true;
 97         }
 98         OUT(ch[x][1]);
 99     }
100     void out(){
101         flag = false;
102         OUT(root);
103         putchar(‘\n‘);
104     }
105     void cut(int a,int b,int c){
106         select(a-1 + 1,0);
107         select(b + 1 + 1,root);
108         int tmp = ch[ch[root][1]][0];
109         ch[ch[root][1]][0] = 0;
110         pushup(ch[root][1]);
111         pushup(root);
112         select(c+1,0);
113         select(c+1+1,root);
114         ch[ch[root][1]][0] = tmp;
115         fa[tmp] = ch[root][1];
116         pushup(ch[root][1]);
117         pushup(root);
118     }
119     void reverse(int L,int R){
120         select(L - 1 + 1,0);
121         select(R + 1 + 1,root);
122         flip[ch[ch[root][1]][0]] ^= 1;
123     }
124 }spt;
125 int main() {
126     char op[10];
127     int n,m,a,b,c;
128     while(~scanf("%d%d",&n,&m)){
129         if(n == -1 && m == -1) break;
130         spt.init(n);
131         for(int i = 1; i <= m; ++i){
132             scanf("%s",op);
133             if(op[0] == ‘C‘){
134                 scanf("%d%d%d",&a,&b,&c);
135                 spt.cut(a,b,c);
136             }else{
137                 scanf("%d%d",&a,&b);
138                 spt.reverse(a,b);
139             }
140         }
141         spt.out();
142     }
143     return 0;
144 }