uva 11922 Permutation Transforme/splay tree，11922permutation
原題鏈接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18902
伸展樹的區間翻轉剪切。。。
如下：
![]()
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 }
View Code
