【HDU】3487 Play with Chain

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define MAXN 300010
  4 using namespace std;
  5 struct SplayTree {
  6     int root, size;
  7     int next[MAXN][2], key[MAXN], pre[MAXN], num[MAXN];
  8     bool flip[MAXN], space;
  9     inline void PushUp(int x) {
 10         num[x] = num[next[x][0]] + num[next[x][1]] + 1;
 11     }
 12     void NewNode(int &x, int father, int val) {
 13         x = ++size;
 14         next[x][0] = next[x][1] = 0;
 15         pre[x] = father;
 16         key[x] = val;
 17         num[x] = 1;
 18         flip[x] = false;
 19     }
 20     void Build(int &x, int L, int R, int father) {
 21         if (L <= R) {
 22             int mid = (L + R) >> 1;
 23             NewNode(x, father, mid);
 24             Build(next[x][0], L, mid - 1, x);
 25             Build(next[x][1], mid + 1, R, x);
 26             PushUp(x);
 27         }
 28     }
 29     void Init(int n) {
 30         root = size = 0;
 31         next[0][0] = next[0][1] = key[0] = pre[0] = num[0] = 0;
 32         flip[0] = space = false;
 33         NewNode(root, 0, -1);
 34         NewNode(next[root][1], root, -1);
 35         num[root]++;
 36         Build(next[next[root][1]][0], 1, n, next[root][1]);
 37         PushUp(next[root][1]);
 38         PushUp(root);
 39     }
 40     inline void PushDown(int x) {
 41         if (flip[x]) {
 42             flip[x] = false;
 43             flip[next[x][0]] ^= true;
 44             flip[next[x][1]] ^= true;
 45             swap(next[x][0], next[x][1]);
 46         }
 47     }
 48     void Rotate(int x, int kind) {
 49         int y, z;
 50         y = pre[x];
 51         z = pre[y];
 52         PushDown(y);
 53         next[y][!kind] = next[x][kind];
 54         pre[next[x][kind]] = y;
 55         next[z][next[z][1] == y] = x;
 56         pre[x] = z;
 57         next[x][kind] = y;
 58         pre[y] = x;
 59         PushUp(y);
 60     }
 61     void Splay(int x, int goal) {
 62         if (x != goal) {
 63             PushDown(x);
 64             while (pre[x] != goal) {
 65                 if (next[pre[x]][0] == x)
 66                     Rotate(x, 1);
 67                 else
 68                     Rotate(x, 0);
 69             }
 70             PushUp(x);
 71             if (!goal)
 72                 root = x;
 73         }
 74     }
 75     int Select(int k) {
 76         int x;
 77         PushDown(root);
 78         for (x = root; num[next[x][0]] + 1 != k;) {
 79             if (num[next[x][0]] + 1 > k)
 80                 x = next[x][0];
 81             else {
 82                 k -= num[next[x][0]] + 1;
 83                 x = next[x][1];
 84             }
 85             PushDown(x);
 86         }
 87         return x;
 88     }
 89     int GetMin(int x) {
 90         PushDown(x);
 91         while (next[x][0]) {
 92             x = next[x][0];
 93             PushDown(x);
 94         }
 95         return x;
 96     }
 97     void Cut(int a, int b, int c) {
 98         int tmp, d;
 99         a = Select(a);
100         b = Select(b + 2);
101         Splay(a, 0);
102         Splay(b, a);
103         tmp = next[b][0];
104         next[b][0] = 0;
105         PushUp(b);
106         PushUp(a);
107         c = Select(c + 1);
108         Splay(c, 0);
109         d = GetMin(next[c][1]);
110         Splay(d, c);
111         next[d][0] = tmp;
112         pre[tmp] = d;
113         PushUp(d);
114         PushUp(c);
115     }
116     void Flip(int a, int b) {
117         a = Select(a);
118         b = Select(b + 2);
119         Splay(a, 0);
120         Splay(b, a);
121         flip[next[b][0]] ^= true;
122     }
123     void InOrder(int x) {
124         if (x) {
125             PushDown(x);
126             InOrder(next[x][0]);
127             if (key[x] > 0) {
128                 if (space)
129                     putchar(' ');
130                 else
131                     space = true;
132                 printf("%d", key[x]);
133             }
134             InOrder(next[x][1]);
135         }
136     }
137 } tree;
138 int main() {
139     char cmd[6];
140     int n, q;
141     int a, b, c;
142     while (scanf("%d%d", &n, &q), n > 0) {
143         tree.Init(n);
144         while (q--) {
145             scanf(" %s%d%d", cmd, &a, &b);
146             if (cmd[0] == 'C') {
147                 scanf("%d", &c);
148                 tree.Cut(a, b, c);
149             } else
150                 tree.Flip(a, b);
151         }
152         tree.InOrder(tree.root);
153         putchar('\n');
154     }
155     return 0;
156 }