ttp://tyvj.cpwz.cn/Problem_Show.asp?id=1730
| 背景 Background | |||
| 此为平衡树系列最后一道：二逼平衡树 | |||
| 描述 Description | |||
| 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数) |
|||
| 输入格式 Input Format | |||
| 第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示有序序列 下面有m行，opt表示操作标号 若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱 若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继 |
|||
| 输出格式 Output Format | |||
| 对于操作1,2,4,5各输出一行，表示查询结果 | |||
| 样例输入 Sample Input [复制数据] | |||
|
9 6 |
|||
| 样例输出 Sample Output [复制数据] | |||
|
2 |
|||
| 时间限制 Time Limitation | |||
| 各个测试点2s | |||
| 注释 Hint | |||
| n,m<=50000 保证有序序列所有值在任何时刻满足[0,10^8] | |||
题解：
线段树套平衡树之神级恶心题………………………………考验人的代码能力的…………………………
View Code
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4
5 using namespace std;
6
7 const int INF=123456789;
8
9 #define lson l,m,rt<<1
10 #define rson m+1,r,rt<<1|1
11
12 const int maxn=50001;
13 const int maxm=maxn*20;
14
15 int min_num,max_num,lastv,z[maxn],n,m,sum;
16
17 int min(int a,int b)
18 {
19 if (a<b) return a;
20 else return b;
21 }
22
23 int max(int a,int b)
24 {
25 if (a>b) return a;
26 else return b;
27 }
28
29 void swap(int &a,int &b)
30 {
31 int c=a;a=b;b=c;
32 }
33
34 struct node
35 {
36 int f,value,l,r,size;
37 node()
38 {
39 f=value=l=r=size=0;
40 }
41 }point[maxm];
42
43 struct splay_tree
44 {
45 node *z;
46 int root,size;
47 splay_tree()
48 {
49 root=size=0;
50 }
51 void build_z(int now)
52 {
53 z=point+now;
54 }
55 void update(int now)
56 {
57 z[now].size=z[z[now].l].size+z[z[now].r].size+1;
58 }
59 void rot_l(int now)
60 {
61 int a=z[now].r;
62 z[now].r=z[a].l;
63 z[a].l=now;
64 update(now);
65 update(a);
66 if (now==root) root=a;
67 else
68 {
69 if (z[z[now].f].l==now) z[z[now].f].l=a;
70 else z[z[now].f].r=a;
71 }
72 z[a].f=z[now].f;
73 z[now].f=a;
74 z[z[now].r].f=now;
75 }
76 void rot_r(int now)
77 {
78 int a=z[now].l;
79 z[now].l=z[a].r;
80 z[a].r=now;
81 update(now);
82 update(a);
83 if (root==now) root=a;
84 else
85 {
86 if (z[z[now].f].l==now) z[z[now].f].l=a;
87 else z[z[now].f].r=a;
88 }
89 z[a].f=z[now].f;
90 z[now].f=a;
91 z[z[now].l].f=now;
92 }
93 void rot_l1(int now)
94 {
95 int a=z[now].r;
96 z[now].r=z[a].l;
97 z[a].l=now;
98 update(now);
99 if (now==root) root=a;
100 else
101 {
102 if (z[z[now].f].l==now) z[z[now].f].l=a;
103 else z[z[now].f].r=a;
104 }
105 z[a].f=z[now].f;
106 z[now].f=a;
107 z[z[now].r].f=now;
108 }
109 void rot_r1(int now)
110 {
111 int a=z[now].l;
112 z[now].l=z[a].r;
113 z[a].r=now;
114 update(now);
115 if (root==now) root=a;
116 else
117 {
118 if (z[z[now].f].l==now) z[z[now].f].l=a;
119 else z[z[now].f].r=a;
120 }
121 z[a].f=z[now].f;
122 z[now].f=a;
123 z[z[now].l].f=now;
124 }
125 void splay(int now,int goal)
126 {
127 while (z[now].f!=goal)
128 {
129 int f=z[now].f;
130 int ff=z[f].f;
131 if (ff==goal)
132 {
133 if (z[f].l==now) rot_r(f);
134 else rot_l(f);
135 }
136 else
137 {
138 if ((z[ff].l==f) && (z[f].l==now))
139 {
140 rot_r(ff);
141 rot_r1(f);
142 }
143 if ((z[ff].r==f) && (z[f].r==now))
144 {
145 rot_l(ff);
146 rot_l1(f);
147 }
148 if ((z[ff].l==f) && (z[f].r==now))
149 {
150 rot_l1(f);
151 rot_r1(ff);
152 }
153 if ((z[ff].r==f) && (z[f].l==now))
154 {
155 rot_r1(f);
156 rot_l1(ff);
157 }
158 }
159 }
160 update(now);
161 if (goal==0) root=now;
162 }
163 void insert(int v,int orz)
164 {
165 if (!orz)
166 {
167 size++;
168 z[size].value=v;
169 z[size].size=1;
170 z[size].l=z[size].r=0;
171 orz=size;
172 }
173 else
174 {
175 size++;
176 z[orz].value=v;
177 z[orz].size=1;
178 z[orz].l=z[orz].r=0;
179 swap(orz,size);
180 }
181 if (root==0) root=size;
182 else
183 {
184 int pos=root,lastp;
185 while (pos)
186 {
187 lastp=pos;
188 z[pos].size++;
189 if (v>z[pos].value) pos=z[pos].r;
190 else pos=z[pos].l;
191 }
192 z[size].f=lastp;
193 if (v>z[lastp].value) z[lastp].r=size;
194 else z[lastp].l=size;
195 splay(size,0);
196 }
197 swap(orz,size);
198 }
199 void replace(int v,int newv)
200 {
201 int now=root;
202 while (now)
203 {
204 if (z[now].value==v) break;
205 if (v>z[now].value) now=z[now].r;
206 else now=z[now].l;
207 }
208 if (z[now].r)
209 {
210 while (z[z[now].r].l)
211 rot_r(z[now].r);
212 z[z[now].r].l=z[now].l;
213 z[z[now].l].f=z[now].r;
214 z[z[now].r].f=z[now].f;
215 if (now==root) root=z[now].r;
216 else
217 {
218 if (z[z[now].f].l==now) z[z[now].f].l=z[now].r;
219 else z[z[now].f].r=z[now].r;
220 }
221 int orz=z[now].r;
222 while (orz)
223 {
224 update(orz);
225 orz=z[orz].f;
226 }
227 }
228 else
229 {
230 if (now==root) root=z[now].l;
231 else
232 {
233 if (z[z[now].f].l==now) z[z[now].f].l=z[now].l;
234 else z[z[now].f].r=z[now].l;
235 }
236 z[z[now].l].f=z[now].f;
237 int orz=z[now].f;
238 while (orz)
239 {
240 update(orz);
241 orz=z[orz].f;
242 }
243 }
244 size--;
245 insert(newv,now);
246 }
247 int get_rank(int v)
248 {
249 int now=root,ans=0;
250 while (now)
251 {
252 if (v>z[now].value) ans+=z[z[now].l].size+1,now=z[now].r;
253 else now=z[now].l;
254 }
255 return ans;
256 }
257 int get_rank2(int v)
258 {
259 int now=root,ans=0;
260 while (now)
261 {
262 if (v>=z[now].value) ans+=z[z[now].l].size+1,now=z[now].r;
263 else now=z[now].l;
264 }
265 return ans;
266 }
267 int query_pre(int v)
268 {
269 int ans=-INF,now=root;
270 while (now)
271 {
272 if (z[now].value<v) ans=max(ans,z[now].value),now=z[now].r;
273 else now=z[now].l;
274 }
275 return ans;
276 }
277 int query_next(int v)
278 {
279 int ans=INF,now=root;
280 while (now)
281 {
282 if (z[now].value>v) ans=min(ans,z[now].value),now=z[now].l;
283 else now=z[now].r;
284 }
285 return ans;
286 }
287 }tree[maxn<<2|1];
288
289 void buildtree(int l,int r,int rt)
290 {
291 if (l==r)
292 {
293 scanf("%d",&z[l]);
294 min_num=min(min_num,z[l]);
295 max_num=max(max_num,z[l]);
296 tree[rt].build_z(sum);
297 tree[rt].insert(z[l],0);
298 sum+=2;
299 return;
300 }
301 int m=(l+r)>>1;
302 buildtree(lson);
303 buildtree(rson);
304 tree[rt].build_z(sum);
305 for (int a=l;a<=r;a++)
306 tree[rt].insert(z[a],0);
307 sum+=r-l+2;
308 }
309
310 void changetree(int l,int r,int rt,int p,int v)
311 {
312 if (l==r)
313 {
314 tree[rt].replace(z[l],v);
315 lastv=z[l];
316 z[l]=v;
317 min_num=min(min_num,z[l]);
318 max_num=max(max_num,z[l]);
319 return;
320 }
321 int m=(l+r)>>1;
322 if (p<=m) changetree(lson,p,v);
323 else changetree(rson,p,v);
324 tree[rt].replace(lastv,v);
325 }
326
327 int get_rank(int l,int r,int rt,int nowl,int nowr,int v)
328 {
329 if ((nowl<=l) && (r<=nowr)) return tree[rt].get_rank(v);
330 int m=(l+r)>>1;
331 int l_rank=0,r_rank=0;
332 if (nowl<=m) l_rank=get_rank(lson,nowl,nowr,v);
333 if (m<nowr) r_rank=get_rank(rson,nowl,nowr,v);
334 return l_rank+r_rank;
335 }
336
337 int get_rank2(int l,int r,int rt,int nowl,int nowr,int v)
338 {
339 if ((nowl<=l) && (r<=nowr)) return tree[rt].get_rank2(v);
340 int m=(l+r)>>1;
341 int l_rank=0,r_rank=0;
342 if (nowl<=m) l_rank=get_rank2(lson,nowl,nowr,v);
343 if (m<nowr) r_rank=get_rank2(rson,nowl,nowr,v);
344 return l_rank+r_rank;
345 }
346
347 int query_pre(int l,int r,int rt,int nowl,int nowr,int v)
348 {
349 if ((nowl<=l) && (r<=nowr)) return tree[rt].query_pre(v);
350 int m=(l+r)>>1;
351 int l_pre=-INF,r_pre=-INF;
352 if (nowl<=m) l_pre=query_pre(lson,nowl,nowr,v);
353 if (m<nowr) r_pre=query_pre(rson,nowl,nowr,v);
354 return max(l_pre,r_pre);
355 }
356
357 int query_next(int l,int r,int rt,int nowl,int nowr,int v)
358 {
359 if ((nowl<=l) && (r<=nowr)) return tree[rt].query_next(v);
360 int m=(l+r)>>1;
361 int l_next=INF,r_next=INF;
362 if (nowl<=m) l_next=query_next(lson,nowl,nowr,v);
363 if (m<nowr) r_next=query_next(rson,nowl,nowr,v);
364 return min(l_next,r_next);
365 }
366
367 int main()
368 {
369 scanf("%d%d",&n,&m);
370 buildtree(1,n,1);
371 for (int a=1;a<=m;a++)
372 {
373 int order;
374 scanf("%d",&order);
375 switch(order)
376 {
377 case 1:
378 {
379 int l,r,k;
380 scanf("%d%d%d",&l,&r,&k);
381 printf("%d\n",get_rank(1,n,1,l,r,k)+1);
382 break;
383 }
384 case 2:
385 {
386 int l,r,k;
387 scanf("%d%d%d",&l,&r,&k);
388 int nowl=min_num-1,nowr=max_num;
389 while (nowl+1!=nowr)
390 {
391 int m=(nowl+nowr)>>1;
392 if (get_rank2(1,n,1,l,r,m)>=k) nowr=m;
393 else nowl=m;
394 }
395 printf("%d\n",nowr);
396 break;
397 }
398 case 3:
399 {
400 int p,v;
401 scanf("%d%d",&p,&v);
402 changetree(1,n,1,p,v);
403 break;
404 }
405 case 4:
406 {
407 int l,r,k;
408 scanf("%d%d%d",&l,&r,&k);
409 printf("%d\n",query_pre(1,n,1,l,r,k));
410 break;
411 }
412 case 5:
413 {
414 int l,r,k;
415 scanf("%d%d%d",&l,&r,&k);
416 printf("%d\n",query_next(1,n,1,l,r,k));
417 break;
418 }
419 }
420 }
421
422 return 0;
423 }