uva 11922 Permutation Transforme/splay tree

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<iostream>
  4 #include<algorithm>
  5 const int Max_N = 100010;
  6 struct Node{
  7     int v, s, rev;
  8     Node *pre, *ch[2];
  9     inline void set(int _v = -1, int _s = 0, Node *p = NULL){
 10         v = _v, s = _s, rev = 0;
 11         pre = ch[0] = ch[1] = p;
 12     }
 13     inline void push_up(){
 14         s = ch[0]->s + ch[1]->s + 1;
 15     }
 16     inline void update(){
 17         rev ^= 1;
 18         std::swap(ch[0], ch[1]);
 19     }
 20     inline void push_down(){
 21         if (rev != 0){
 22             rev ^= 1;
 23             ch[0]->update();
 24             ch[1]->update();
 25         }
 26     }
 27 };
 28 struct SplayTree{
 29     int N = 0;
 30     Node *tail, *root, *null, stack[Max_N];
 31     void init(int n){
 32         N = n, tail = &stack[0];
 33         null = tail++;
 34         null->set();
 35         root = newNode(-1);
 36         root->ch[1] = newNode(-1);
 37         root->ch[1]->pre = root;
 38         Node *x = built(1, n);
 39         root->ch[1]->ch[0] = x;
 40         x->pre = root->ch[1];
 41         root->ch[1]->push_up();
 42         root->push_up();
 43     }
 44     inline Node *newNode(int v){
 45         Node *p = tail++;
 46         p->set(v, 1, null);
 47         return p;
 48     }
 49     Node *built(int l, int r){
 50         if (l > r) return null;
 51         int mid = (l + r) >> 1;
 52         Node *p = newNode(mid);
 53         p->ch[0] = built(l, mid - 1);
 54         if (p->ch[0] != null) p->ch[0]->pre = p;
 55         p->ch[1] = built(mid + 1, r);
 56         if (p->ch[1] != null) p->ch[1]->pre = p;
 57         p->push_up();
 58         return p;
 59     }
 60     inline void rotate(Node *x, int c){
 61         Node *y = x->pre;
 62         y->push_down(), x->push_down();
 63         y->ch[!c] = x->ch[c];
 64         x->pre = y->pre;
 65         if (x->ch[c] != null) x->ch[c]->pre = y;
 66         if (y->pre != null) y->pre->ch[y->pre->ch[0] != y] = x;
 67         x->ch[c] = y;
 68         y->pre = x;
 69         y->push_up();
 70         if (y == root) root = x;
 71     }
 72     inline void splay(Node *x, Node *f){
 73         if (x == root) return;
 74         for (; x->pre != f; x->push_down()){
 75             if (x->pre->pre == f){
 76                 rotate(x, x->pre->ch[0] == x);
 77             } else {
 78                 Node *y = x->pre, *z = y->pre;
 79                 if (z->ch[0] == y){
 80                     if (y->ch[0] == x) 
 81                         rotate(y, 1), rotate(x, 1);
 82                     else rotate(x, 0), rotate(x, 1);
 83                 } else {
 84                     if (y->ch[1] == x) 
 85                         rotate(y, 0), rotate(x, 0);
 86                     else rotate(x, 1), rotate(x, 0);
 87                 }
 88             }
 89         }
 90         x->push_up();
 91     }
 92     inline Node *select(Node *x, int k){
 93         for (int t = 0; x != null;){
 94             x->push_down();
 95             t = x->ch[0]->s;
 96             if (t == k) break;
 97             else if (k < t) x = x->ch[0];
 98             else k -= t + 1, x = x->ch[1];
 99         }
100         return x;
101     }
102     inline Node *get_range(int l, int r){
103         splay(select(root, l - 1), null);
104         splay(select(root, r + 1), root);
105         return root->ch[1]->ch[0];
106     }
107     inline Node *reverse(int l, int r){
108         Node *x = get_range(l, r);
109         x->update();
110         return x;
111     }
112     inline void cut_link(int l, int r){
113         Node *x = reverse(l, r);
114         root->ch[1]->ch[0] = null;
115         root->ch[1]->push_up();
116         root->push_up();
117         int  k = N - r + l - 1;
118         get_range(1, k);
119         splay(select(root, k), null);
120         splay(select(root, k + 1), root);
121         root->ch[1]->ch[0] = x;
122         x->pre = root->ch[1];
123         root->ch[1]->push_up();
124         root->push_up();
125     }
126     inline void travle(Node *x){
127         if (x != null){
128             x->push_down();
129             travle(x->ch[0]);
130             printf("%d\n", x->v);
131             travle(x->ch[1]);
132         }
133     }
134     inline void travle(){
135         get_range(1, N);
136         Node *x = root->ch[1]->ch[0];
137         travle(x);
138     }
139 }Splay;
140 int main(){
141 #ifdef LOCAL
142     freopen("in.txt", "r", stdin);
143     freopen("out.txt", "w+", stdout);
144 #endif
145     int a, b, n, m;
146     while (~scanf("%d %d", &n, &m)){
147         Splay.init(n);
148         while (m--){
149             scanf("%d %d", &a, &b);
150             Splay.cut_link(a, b);
151         }
152         Splay.travle();
153     }
154     return 0;
155 }