实现功能:同平衡树Treap 1(BZOJ3224 / tyvj1728)
这次的模板有了不少的改进,显然更加美观了,几乎每个部分都有了不少简化,尤其是删除部分,这个参照了hzwer神犇的写法,在此鸣谢,然后,贴模板走人
1 var
2 i,j,k,l,m,n,head,tot:longint;
3 a,b,lef,rig,fix:array[0..100010] of longint;
4 function min(x,y:longint):longint;
5 begin
6 if x<y then min:=x else min:=y;
7 end;
8 function max(x,y:longint):longint;
9 begin
10 if x>y then max:=x else max:=y;
11 end;
12 procedure lt(var x:longint);
13 var f,r:longint;
14 begin
15 if (x=0) or (rig[x]=0) then exit;
16 b[rig[x]]:=b[x];b[x]:=b[lef[x]]+b[lef[rig[x]]]+1;
17 f:=x;r:=rig[x];
18 rig[f]:=lef[r];
19 lef[r]:=f;
20 x:=r;
21 end;
22 procedure rt(var x:longint);
23 var f,l:longint;
24 begin
25 if (x=0) or (lef[x]=0) then exit;
26 b[lef[x]]:=b[x];b[x]:=b[rig[x]]+b[rig[lef[x]]]+1;
27 f:=x;l:=lef[x];
28 lef[f]:=rig[l];
29 rig[l]:=f;
30 x:=l;
31 end;
32 function newp(x:longint):longint;
33 begin
34 inc(tot);newp:=tot;
35 a[tot]:=x;b[tot]:=1;
36 lef[tot]:=0;rig[tot]:=0;
37 fix[tot]:=random(maxlongint);
38 end;
39 procedure ins(var x:longint;y:longint);
40 begin
41 if x=0 then
42 begin
43 x:=newp(y);
44 exit;
45 end;
46 if y<a[x] then
47 begin
48 ins(lef[x],y);b[x]:=b[lef[x]]+b[rig[x]]+1;
49 if fix[lef[x]]<fix[x] then rt(x);
50 end
51 else
52 begin
53 ins(rig[x],y);b[x]:=b[lef[x]]+b[rig[x]]+1;
54 if fix[rig[x]]<fix[x] then lt(x);
55 end;
56 end;
57 procedure del(var x:longint;y:longint);
58 begin
59 if x=0 then exit;
60 if a[x]=y then
61 begin
62 if lef[x]=0 then x:=rig[x] else
63 if rig[x]=0 then x:=lef[x] else
64 if fix[lef[x]]>fix[rig[x]] then
65 begin
66 lt(x);del(lef[x],y);
67 b[x]:=b[lef[x]]+b[rig[x]]+1;
68 end
69 else
70 begin
71 rt(x);del(rig[x],y);
72 b[x]:=b[lef[x]]+b[rig[x]]+1;
73 end;
74 end
75 else if y<a[x] then
76 begin
77 del(lef[x],y);
78 b[x]:=b[lef[x]]+b[rig[x]]+1;
79 end
80 else begin
81 del(rig[x],y);
82 b[x]:=b[lef[x]]+b[rig[x]]+1;
83 end;
84 end;
85 function getrank(x,y:longint):longint;
86 begin
87 if x=0 then exit(0);
88 if y>a[x] then exit(b[lef[x]]+1+getrank(rig[x],y)) else exit(getrank(lef[x],y));
89 end;
90 function rankget(x,y:longint):longint;
91 begin
92 if y=(b[lef[x]]+1) then exit(a[x]);
93 if y<(b[lef[x]]+1) then exit(rankget(lef[x],y)) else exit(rankget(rig[x],y-1-b[lef[x]]));
94 end;
95 function getpre(x,y:longint):longint;
96 begin
97 if x=0 then exit(-maxlongint);
98 if a[x]<y then exit(max(a[x],getpre(rig[x],y))) else exit(getpre(lef[x],y));
99 end;
100 function getsuc(x,y:longint):longint;
101 begin
102 if x=0 then exit(maxlongint);
103 if a[x]>y then exit(min(a[x],getsuc(lef[x],y))) else exit(getsuc(rig[x],y));
104 end;
105 begin
106 readln(n);tot:=0;head:=0;
107 for i:=1 to n do
108 begin
109 readln(j,k);
110 case j of
111 1:ins(head,k);
112 2:del(head,k);
113 3:writeln(getrank(head,k)+1);
114 4:writeln(rankget(head,k));
115 5:writeln(getpre(head,k));
116 6:writeln(getsuc(head,k));
117 end;
118 end;
119 end.