Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2566 Solved: 1031
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x,且最大的数) 6. 求x的后继(后继定义为大于x,且最小的数)
第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)
对于操作3,4,5,6每行输出一个数,表示对应答案
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
106465 84185 492737
1.n的数据范围:n<=100000
2.每个数的数据范围:[-1e7,1e7]
题解:这是一道平衡树裸题,我果断还是用我萌萌哒Treap,可是在大视野上交就在不停的WA。。。然后弄到数据后发现总是3操作(查询x数的排名)求得的值多出那么几名(HansBug:啊啊啊啊啊啊。。。这个问题让我纠结了一晚上且第二天就病倒了有木有TT phile:这种水题我也是醉了)——仔细一想,我原来程序里面3操作(本程序中的getrank操作)忘考虑一种可能了——当当前节点=x时,不见得最佳排名就是当前点的排名(题目中要的是最优排名哦),我最初写的时候虽然也想到了,可是在插入操作时我是规定只有小于当前点的点才能去左边的啊——可是更重要的是,就算你ins严格遵守了这一规则,但是完全有可能在删除操作中被打乱了——也就是说经过了无数次折腾之后的树未必完全符合插入操作时的规则。。。这样子问题就解决了,别的不难写。。。(HansBug:这个问题估计会坑到无数的treap党有木有。。。希望大家引以为戒么么哒,还有代码有点长么么哒)
1 var
2 i,j,k,l,m,n,head,ts:longint;f1:text;
3 a,b,fix,lef,rig:array[0..500000] of longint;
4 procedure lt(var x:longint);inline;
5 var f,r:longint;
6 begin
7 if (x=0) or (rig[x]=0) then exit;
8 f:=x;r:=rig[x];
9 b[r]:=b[f];
10 b[f]:=b[lef[f]]+1+b[LEF[R]];
11 rig[f]:=lef[r];
12 lef[r]:=f;
13 x:=r;
14 end;
15 procedure rt(var x:longint);inline;
16 var f,l:longint;
17 begin
18 if (x=0) or (lef[x]=0) then exit;
19 f:=x;l:=lef[x];
20 b[l]:=b[f];
21 b[f]:=b[rig[f]]+1+b[rig[l]];
22 lef[f]:=rig[l];
23 rig[l]:=f;
24 x:=l;
25 end;
26 FUNCTION max(x,y:longint):longint;inline;
27 begin
28 if x>y then max:=x else max:=y;
29 end;
30 function min(x,y:longint):longint;inline;
31 begin
32 if x<y then min:=x else min:=y;
33 end;
34 procedure ins(var head:longint;x:longint);
35 begin
36 if head=0 then
37 begin
38 head:=x;
39 exit;
40 end;
41 if a[x]<a[head] then
42 begin
43 if lef[head]=0 then lef[head]:=x else ins(lef[head],x);
44 b[head]:=b[lef[head]]+b[rig[head]]+1;
45 if fix[lef[head]]<fix[head] then rt(head);
46 end
47 else
48 begin
49 if rig[head]=0 then rig[head]:=x else ins(rig[head],x);
50 b[head]:=b[lef[head]]+b[rig[head]]+1;
51 if fix[rig[head]]<fix[head] then lt(head);
52 end;
53 end;
54 function getp(head,x:longint):longint;
55 begin
56 if head=0 then exit(0);
57 if a[head]=x then exit(head);
58 if a[head]>x then exit(getp(lef[head],x)) else exit(getp(rig[head],x));
59 end;
60 procedure del(var head:longint);
61 var i,j,k,l,f,r:longint;
62 begin
63 if head=0 then exit;
64 if (lef[head]=0) then
65 begin
66 b[head]:=b[rig[head]];
67 head:=rig[head];
68 exit;
69 end;
70 if rig[head]=0 then
71 begin
72 b[head]:=b[lef[head]];
73 head:=lef[head];
74 exit;
75 end;
76 if fix[lef[head]]>fix[rig[head]] then
77 begin
78 lt(head);
79 del(lef[head]);
80 b[head]:=b[lef[head]]+b[rig[head]]+1;
81 end
82 else
83 begin
84 rt(head);
85 del(rig[head]);
86 b[head]:=b[lef[head]]+b[rig[head]]+1;
87 end;
88 end;
89 procedure det(var head,x:longint);
90 begin
91 if head=0 then exit;
92 if x=head then
93 begin
94 del(head);
95 b[head]:=b[lef[head]]+b[rig[head]]+1;
96 exit;
97 end;
98 if lef[head]=x then
99 begin
100 del(lef[head]);
101 b[head]:=b[lef[head]]+b[rig[head]]+1;
102 exit;
103 end;
104 if rig[head]=x then
105 begin
106 del(rig[head]);
107 b[head]:=b[lef[head]]+b[rig[head]]+1;
108 exit;
109 end;
110 if a[x]<a[head] then det(lef[head],x) else det(rig[head],x);
111 b[head]:=b[lef[head]]+b[rig[head]]+1;
112 end;
113 procedure showoff(head:longint);
114 begin
115 if head=0 then exit;
116 showoff(lef[head]);
117 write(a[head],' ');
118 showoff(rig[head]);
119 end;
120 function getrank(head,x:longint):longint;
121 var k:longint;
122 begin
123 if head=0 then exit(-1);
124 if x=a[head] then //亲们注意了,就是这个地方坑了我好久啊啊啊啊啊啊
125 begin
126 k:=getrank(lef[head],x);
127 if k=-1 then exit(b[lef[head]]+1) else exit(k);
128 end
129 else
130 begin
131 if x<a[head] then
132 begin
133 exit(getrank(lef[head],x));
134 end
135 else
136 begin
137 k:=getrank(rig[head],x);
138 if k=-1 then exit(-1) else exit(b[lef[head]]+1+k);
139 end;
140 end;
141 end;
142 function rankget(head,x:longint):longint;
143 begin
144 if head=0 then exit(maxlongint);
145 if (b[lef[head]]+1)=x then exit(a[head]);
146 if (b[lef[head]]+1)<x then exit(rankget(rig[head],x-1-b[lef[head]])) else exit(rankget(lef[head],x))
147 end;
148 function getsuc(head,x:longint):longint;
149 begin
150 if (head=0) then exit(+maxlongint);
151 if (a[head]<=x) then exit(getsuc(rig[head],x)) else exit(min(a[head],getsuc(lef[head],x)));
152 end;
153 function getpre(head,x:longint):longint;
154 begin
155 if (head=0) then exit(-maxlongint);
156 if (a[head]>=x) then exit(getpre(lef[head],x)) else exit(max(a[head],getpre(rig[head],x)));
157 end;
158
159 begin
160 m:=0;head:=0;
161 randomize;
162 readln(n);
163 for i:=1 to n do
164 begin
165 read(l);
166 case l of
167 1:begin
168 readln(j);
169 inc(m);
170 a[m]:=j;
171 fix[m]:=random(maxlongint);
172 lef[m]:=0;rig[m]:=0;b[m]:=1;
173 ins(head,m);
174 end;
175 2:begin
176 readln(j);
177 k:=getp(head,j);
178 det(head,k);
179 l:=0;
180 end;
181 3:BEGIN
182 readln(j);
183 k:=getrank(head,j);
184 writeln(k);
185 end;
186 4:begin
187 readln(j);
188 writeln(rankget(head,j));
189 end;
190 5:begin
191 readln(j);
192 writeln(getpre(head,j));
193 end;
194 6:begin
195 readln(j);
196 writeln(getsuc(head,j));
197 end;
198 end;
199
200 l:=0;
201 end;
202 readln;
203 end.
204