实现功能如下——1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
本程序的实现原理为Treap平衡树
详见BZOJ3224
var
i,j,k,l,m,n,head,ts:longint;f1:text;
a,b,fix,lef,rig:array[..] of longint;
procedure lt(var x:longint);inline;
var f,r:longint;
begin
if (x=) or (rig[x]=) then exit;
f:=x;r:=rig[x];
b[r]:=b[f];
b[f]:=b[lef[f]]++b[LEF[R]];
rig[f]:=lef[r];
lef[r]:=f;
x:=r;
end;
procedure rt(var x:longint);inline;
var f,l:longint;
begin
if (x=) or (lef[x]=) then exit;
f:=x;l:=lef[x];
b[l]:=b[f];
b[f]:=b[rig[f]]++b[rig[l]];
lef[f]:=rig[l];
rig[l]:=f;
x:=l;
end;
FUNCTION max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
procedure ins(var head:longint;x:longint);
begin
if head= then
begin
head:=x;
exit;
end;
if a[x]<a[head] then
begin
ins(lef[head],x);
b[head]:=b[lef[head]]+b[rig[head]]+;
if fix[lef[head]]<fix[head] then rt(head);
end
else
begin
ins(rig[head],x);
b[head]:=b[lef[head]]+b[rig[head]]+;
if fix[rig[head]]<fix[head] then lt(head);
end;
end;
function getp(head,x:longint):longint;
begin
if head= then exit();
if a[head]=x then exit(head);
if a[head]>x then exit(getp(lef[head],x)) else exit(getp(rig[head],x));
end;
procedure del(var head:longint);
var i,j,k,l,f,r:longint;
begin
if head= then exit;
if (lef[head]=) then
begin
b[head]:=b[rig[head]];
head:=rig[head];
exit;
end;
if rig[head]= then
begin
b[head]:=b[lef[head]];
head:=lef[head];
exit;
end;
if fix[lef[head]]>fix[rig[head]] then
begin
lt(head);
del(lef[head]);
b[head]:=b[lef[head]]+b[rig[head]]+;
end
else
begin
rt(head);
del(rig[head]);
b[head]:=b[lef[head]]+b[rig[head]]+;
end;
end;
procedure det(var head,x:longint);
begin
if head= then exit;
if x=head then
begin
del(head);
b[head]:=b[lef[head]]+b[rig[head]]+;
exit;
end;
if lef[head]=x then
begin
del(lef[head]);
b[head]:=b[lef[head]]+b[rig[head]]+;
exit;
end;
if rig[head]=x then
begin
del(rig[head]);
b[head]:=b[lef[head]]+b[rig[head]]+;
exit;
end;
if a[x]<a[head] then det(lef[head],x) else det(rig[head],x);
b[head]:=b[lef[head]]+b[rig[head]]+;
end;
procedure showoff(head:longint);
begin
if head= then exit;
showoff(lef[head]);
write(a[head],' ');
showoff(rig[head]);
end;
function getrank(head,x:longint):longint;
var k:longint;
begin
if head= then exit(-);
if x=a[head] then //亲们注意了，就是这个地方坑了我好久啊啊啊啊啊啊
begin
k:=getrank(lef[head],x);
if k=- then exit(b[lef[head]]+) else exit(k);
end
else
begin
if x<a[head] then
begin
exit(getrank(lef[head],x));
end
else
begin
k:=getrank(rig[head],x);
if k=- then exit(-) else exit(b[lef[head]]++k);
end;
end;
end;
function rankget(head,x:longint):longint;
begin
if head= then exit(maxlongint);
if (b[lef[head]]+)=x then exit(a[head]);
if (b[lef[head]]+)<x then exit(rankget(rig[head],x--b[lef[head]])) else exit(rankget(lef[head],x))
end;
function getsuc(head,x:longint):longint;
begin
if (head=) then exit(+maxlongint);
if (a[head]<=x) then exit(getsuc(rig[head],x)) else exit(min(a[head],getsuc(lef[head],x)));
end;
function getpre(head,x:longint):longint;
begin
if (head=) then exit(-maxlongint);
if (a[head]>=x) then exit(getpre(lef[head],x)) else exit(max(a[head],getpre(rig[head],x)));
end; begin
m:=;head:=;
randomize;
readln(n);
for i:= to n do
begin
read(l);
case l of
:begin
readln(j);
inc(m);
a[m]:=j;
fix[m]:=random(maxlongint);
lef[m]:=;rig[m]:=;b[m]:=;
ins(head,m);
end;
:begin
readln(j);
k:=getp(head,j);
det(head,k);
l:=;
end;
:BEGIN
readln(j);
k:=getrank(head,j);
writeln(k);
end;
:begin
readln(j);
writeln(rankget(head,j));
end;
:begin
readln(j);
writeln(getpre(head,j));
end;
:begin
readln(j);
writeln(getsuc(head,j));
end;
end; l:=;
end;
readln;
end.