比較模闆的splay題
cut操作和reverse操作。
1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4
5 using namespace std;
6
7 #define Key_value ch[ch[root][1] ][0]
8
9 const int maxn = 5e5+10;
10 const int INF = 0x3f3f3f3f;
11
12 int pre[maxn],ch[maxn][2],key[maxn],sz[maxn];
13 int root,tot1;
14 int rev[maxn],mi[maxn],add[maxn];
15 int s[maxn],tot2;
16 int a[maxn],cnt;
17 int n,q;
18
19 void Treavel(int x)
20 {
21 if(x)
22 {
23 Treavel(ch[x][0]);
24 printf("結點:%2d: 左兒子 %2d 右兒子 %2d 父結點 %2d key=%2d size= %2d mi=%2d add=%2d\n",x,ch[x][0],ch[x][1],pre[x],key[x],sz[x],mi[x],add[x]);
25 Treavel(ch[x][1]);
26 }
27 }
28 void debug()
29 {
30 printf("root:%d\n",root);
31 Treavel(root);
32 }
33 //
34
35 void NewNode(int &r,int father,int k)
36 {
37 if(tot2) r = s[tot2--];
38 else r = ++tot1;
39 pre[r] = father;
40 ch[r][0] = ch[r][1] = 0;
41 key[r] = k;
42 mi[r] = k;
43 rev[r] = add[r] = 0;
44 sz[r] = 1;
45 }
46
47 void Update_add(int r,int c)
48 {
49 if(!r) return ;
50 key[r] += c;
51 mi[r] += c;
52 add[r] += c;
53 }
54
55 void Update_rev(int r)
56 {
57 if(!r) return ;
58 swap(ch[r][0],ch[r][1]);
59 rev[r] ^= 1;
60 }
61
62 void push_up(int r)
63 {
64 int lson = ch[r][0],rson = ch[r][1];
65 sz[r] = sz[lson] + sz[rson] + 1;
66 mi[r] = min(min(mi[lson],mi[rson]),key[r]);
67 }
68
69 void push_down(int r)
70 {
71 if(rev[r])
72 {
73 Update_rev(ch[r][0]);
74 Update_rev(ch[r][1]);
75 rev[r] = 0;
76 }
77 if(add[r])
78 {
79 Update_add(ch[r][0],add[r]);
80 Update_add(ch[r][1],add[r]);
81 add[r] = 0;
82 }
83 }
84
85 void Build(int &x,int l,int r,int father)
86 {
87 if(l>r) return ;
88 int mid = (l+r)>>1;
89 NewNode(x,father,a[mid]);
90 Build(ch[x][0],l,mid-1,x);
91 Build(ch[x][1],mid+1,r,x);
92 push_up(x);
93 }
94
95 void Init()
96 {
97 root = tot1 = tot2 = 0;
98 ch[root][0] = ch[root][1] = sz[root] = pre[root] = 0;
99 rev[root] = key[root] = 0;
100 mi[root] = INF;
101 NewNode(root,0,0);
102 NewNode(ch[root][1],root,0);
103 for(int i=1;i<=n;i++) a[i] = i;
104 Build(Key_value,1,n,ch[root][1]);
105 push_up(ch[root][1]);
106 push_up(root);
107 }
108 void Rotate(int x,int kind)
109 {
110 int y = pre[x];
111 push_down(y);
112 push_down(x);
113 ch[y][!kind] = ch[x][kind];
114 pre[ch[x][kind] ] = y;
115 if(pre[y])
116 ch[pre[y] ][ch[pre[y]][1]==y ] = x;
117 pre[x] = pre[y];
118 ch[x][kind] = y;
119 pre[y] = x;
120 push_up(y);
121 }
122 void Splay(int r,int goal)
123 {
124 push_down(r);
125 while(pre[r] != goal)
126 {
127 if(pre[pre[r] ] == goal)
128 {
129 push_down(pre[r]);
130 push_down(r);
131 Rotate(r,ch[pre[r]][0] == r);
132 }
133 else
134 {
135 push_down(pre[pre[r] ]);
136 push_down(pre[r]);
137 push_down(r);
138 int y = pre[r];
139 int kind = ch[pre[y] ][0] == y;
140 if(ch[y][kind] == r)
141 {
142 Rotate(r,!kind);
143 Rotate(r,kind);
144 }
145 else
146 {
147 Rotate(y,kind);
148 Rotate(r,kind);
149 }
150 }
151 push_up(r);
152 if(goal == 0) root = r;
153 }
154 }
155
156 int Get_kth(int r,int k)
157 {
158 push_down(r);
159 int t = sz[ch[r][0] ] + 1;
160 if(t == k) return r;
161 if(t > k) return Get_kth(ch[r][0],k);
162 else return Get_kth(ch[r][1],k-t);
163 }
164
165 void Insert(int pos,int tot)
166 {
167 for(int i=0;i<tot;i++) scanf("%d",&a[i]);
168 Splay(Get_kth(root,pos+1) , 0);
169 Splay(Get_kth(root,pos+2) , root);
170 Build(Key_value,0,tot-1,ch[root][1]);
171 push_up(ch[root][1]);
172 push_up(root);
173 }
174 void erase(int r)
175 {
176 if(!r) return ;
177 s[++tot2] = r;
178 erase(ch[r][0]);
179 erase(ch[r][1]);
180 }
181 void Delete(int pos,int tot)
182 {
183 Splay(Get_kth(root,pos) ,0);
184 Splay(Get_kth(root,pos+tot+1) , root);
185 erase(Key_value);
186 pre[Key_value] = 0;
187 Key_value = 0;
188 push_up(ch[root][1]);
189 push_up(root);
190 }
191
192 void Reverse(int pos,int tot)
193 {
194 Splay(Get_kth(root,pos) , 0);
195 Splay(Get_kth(root,pos+tot+1), root);
196 Update_rev(Key_value);
197 }
198
199 void Add(int pos,int tot,int c)
200 {
201 Splay(Get_kth(root,pos) , 0);
202 Splay(Get_kth(root,pos+tot+1) , root);
203 Update_add(Key_value,c);
204 push_up(ch[root][1]);
205 push_up(root);
206 }
207
208 int Get_min(int pos,int tot)
209 {
210 Splay(Get_kth(root,pos) , 0);
211 Splay(Get_kth(root,pos+tot+1) , root);
212 return mi[Key_value];
213 }
214
215 void Revolve(int l,int r,int t)
216 {
217 if(!t) return ;
218 int c = r - t;
219 Splay(Get_kth(root,l) , 0);
220 Splay(Get_kth(root,c+2),root);
221 int tmp = Key_value;
222 Key_value = 0;
223 push_up(ch[root][1]);
224 push_up(root);
225 Splay(Get_kth(root,r-c+l) , 0);
226 Splay(Get_kth(root,r-c+l+1) , root);
227 Key_value = tmp;
228 pre[Key_value] = ch[root][1];
229 push_up(ch[root][1]);
230 push_up(root);
231 }
232
233 void Cut(int pos,int tot,int n_pos)
234 {
235 //printf("%d %d\n",Get_kth(root,pos),Get_kth(root,pos+tot+1));
236 Splay(Get_kth(root,pos) , 0);
237 Splay(Get_kth(root,pos+tot+1) , root);
238 int tmp = Key_value;
239 Key_value = 0;
240 push_up(ch[root][1]);
241 push_up(root);
242
243 Splay(Get_kth(root,n_pos+1) , 0);
244 Splay(Get_kth(root,n_pos+2) , root);
245 Key_value = tmp;
246 pre[Key_value] = ch[root][1];
247 push_up(ch[root][1]);
248 push_up(root);
249 }
250
251 void InOrder(int r)
252 {
253 if(!r ) return ;
254 push_down(r);
255 InOrder(ch[r][0]);
256 if(key[r]) a[cnt++] = key[r];
257 InOrder(ch[r][1]);
258 }
259
260 int m;
261 int main()
262 {
263 while(scanf("%d%d",&n,&m))
264 {
265 if(n == -1) return -1;
266 Init();
267 //debug();
268 char op[10];
269 int x,y,z;
270 for(int i=0;i<m;i++)
271 {
272 scanf("%s",op);
273 if(op[0] == 'F')
274 {
275 scanf("%d%d",&x,&y);
276 Reverse(x,y-x+1);
277 }
278 else if(op[0] == 'C')
279 {
280 scanf("%d%d%d",&x,&y,&z);
281 Cut(x,y-x+1,z);
282 }
283 }
284 cnt = 0;
285 InOrder(root);
286 for(int i=0;i<cnt;i++)
287 {
288 printf("%d%s",a[i],(i==cnt-1) ? "":" ");
289 }
290 printf("\n");
291 }
292 } 轉載于:https://www.cnblogs.com/helica/p/5506019.html