bzoj 1269 [AHOI2006]文本編輯器editor，
原題鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=1269
伸展樹的運用，如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using std::swap;
7 const int Max_N = 3000010;
8 struct Node{
9 char chr;
10 int s;
11 bool rev;
12 Node *pre, *ch[2];
13 inline void
14 set(char _chr = ' ', int _s = 0, Node *p = NULL){
15 chr = _chr, s = _s, rev = 0;
16 pre = ch[0] = ch[1] = p;
17 }
18 inline void push_up(){
19 s = ch[0]->s + ch[1]->s + 1;
20 }
21 inline void update(){
22 rev ^= 1;
23 swap(ch[0], ch[1]);
24 }
25 inline void push_down(){
26 if (rev != 0){
27 rev ^= 1;
28 ch[0]->update();
29 ch[1]->update();
30 }
31 }
32 };
33 struct SplayTree{
34 char buf[Max_N];
35 Node *tail, *root, *null;
36 Node stack[Max_N], *store[Max_N];
37 int top, pos;
38 void init(){
39 top = 0, pos = 0;
40 tail = &stack[0];
41 null = tail++;
42 null->set();
43 root = newNode(' ');
44 root->ch[1] = newNode(' ');
45 root->ch[1]->pre = root;
46 root->ch[1]->push_up();
47 root->push_up();
48 }
49 inline Node *newNode(char chr){
50 Node *p = null;
51 if (!top) p = tail++;
52 else p = store[--top];
53 p->set(chr, 1, null);
54 return p;
55 }
56 inline void rotate(Node *x, int c){
57 Node *y = x->pre;
58 y->push_down(), x->push_down();
59 y->ch[!c] = x->ch[c];
60 x->pre = y->pre;
61 if (x->ch[c] != null) x->ch[c]->pre = y;
62 if (y->pre != null) y->pre->ch[y->pre->ch[0] != y] = x;
63 x->ch[c] = y;
64 y->pre = x;
65 y->push_up();
66 if (y == root) root = x;
67 }
68 inline void splay(Node *x, Node *f){
69 if (x == root) return;
70 for (; x->pre != f; x->push_down()){
71 if (x->pre->pre == f){
72 rotate(x, x->pre->ch[0] == x);
73 } else {
74 Node *y = x->pre, *z = y->pre;
75 if (z->ch[0] == y){
76 if (y->ch[0] == x)
77 rotate(y, 1), rotate(x, 1);
78 else rotate(x, 0), rotate(x, 1);
79 } else {
80 if (y->ch[1] == x)
81 rotate(y, 0), rotate(x, 0);
82 else rotate(x, 1), rotate(x, 0);
83 }
84 }
85 }
86 x->push_up();
87 }
88 inline Node *built(int l, int r){
89 if (l > r) return null;
90 int mid = (l + r) >> 1;
91 Node *p = newNode(buf[mid]);
92 p->ch[0] = built(l, mid - 1);
93 if (p->ch[0] != null) p->ch[0]->pre = p;
94 p->ch[1] = built(mid + 1, r);
95 if (p->ch[1] != null) p->ch[1]->pre = p;
96 p->push_up();
97 return p;
98 }
99 inline void recycle(Node *x){
100 if (x != null){
101 recycle(x->ch[0]);
102 store[top++] = x;
103 recycle(x->ch[1]);
104 }
105 }
106 inline Node *select(Node *x, int k){
107 for (int t = 0; x != null;){
108 x->push_down();
109 t = x->ch[0]->s;
110 if (k == t + 1) break;
111 else if (k <= t) x = x->ch[0];
112 else k -= t + 1, x = x->ch[1];
113 }
114 return x;
115 }
116 inline void get_range(int x, int y){
117 splay(select(root, x + 1), null);
118 splay(select(root, y + 2), root);
119 }
120 inline void Gets(char *s){
121 char c;
122 while (c = getchar(), c != '\n') *s++ = c;
123 *s = '\0';
124 }
125 inline void insert(int n){
126 char c;
127 scanf("%c", &c);
128 Gets(buf + 1);
129 get_range(pos, pos);
130 Node *ret = built(1, n);
131 root->ch[1]->ch[0] = ret;
132 ret->pre = root->ch[1];
133 root->ch[1]->push_up();
134 root->push_up();
135 }
136 inline void del(int n){
137 get_range(pos, pos + n);
138 Node* &ret = root->ch[1];
139 ret->ch[0]->pre = null;
140 #ifdef LOCAL
141 recycle(ret->ch[0]);
142 #endif
143 ret->ch[0] = null;
144 ret->push_up();
145 root->push_up();
146 }
147 inline void rotate(int n){
148 get_range(pos, pos + n);
149 root->ch[1]->ch[0]->update();
150 }
151 inline void get(){
152 splay(select(root, pos + 2), null);
153 printf("%c\n", root->chr);
154 }
155 inline void move(){
156 scanf("%d", &pos);
157 }
158 inline void prev(){
159 pos--;
160 }
161 inline void next(){
162 pos++;
163 }
164 }spt;
165 int main(){
166 #ifdef LOCAL
167 freopen("in.txt", "r", stdin);
168 freopen("out.txt", "w+", stdout);
169 #endif
170 spt.init();
171 int m, n;
172 char str[100];
173 scanf("%d", &m);
174 while (m--){
175 scanf("%s", str);
176 switch (str[0]){
177 case 'M':
178 spt.move();
179 break;
180 case 'I':
181 scanf("%d", &n);
182 spt.insert(n);
183 break;
184 case 'D':
185 scanf("%d", &n);
186 spt.del(n);
187 break;
188 case 'N':
189 spt.next();
190 break;
191 case 'P':
192 spt.prev();
193 break;
194 case 'R':
195 scanf("%d", &n);
196 spt.rotate(n);
197 break;
198 case 'G':
199 spt.get();
200 break;
201 }
202 }
203 return 0;
204 }
View Code
