实现功能：同平衡树Treap 1（BZOJ3224 / tyvj1728）
这次的模板有了不少的改进，显然更加美观了，几乎每个部分都有了不少简化，尤其是删除部分，这个参照了hzwer神犇的写法，在此鸣谢，然后，贴模板走人
var
i,j,k,l,m,n,head,tot:longint;
a,b,lef,rig,fix:array[..] of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
procedure lt(var x:longint);
var f,r:longint;
begin
if (x=) or (rig[x]=) then exit;
b[rig[x]]:=b[x];b[x]:=b[lef[x]]+b[lef[rig[x]]]+;
f:=x;r:=rig[x];
rig[f]:=lef[r];
lef[r]:=f;
x:=r;
end;
procedure rt(var x:longint);
var f,l:longint;
begin
if (x=) or (lef[x]=) then exit;
b[lef[x]]:=b[x];b[x]:=b[rig[x]]+b[rig[lef[x]]]+;
f:=x;l:=lef[x];
lef[f]:=rig[l];
rig[l]:=f;
x:=l;
end;
function newp(x:longint):longint;
begin
inc(tot);newp:=tot;
a[tot]:=x;b[tot]:=;
lef[tot]:=;rig[tot]:=;
fix[tot]:=random(maxlongint);
end;
procedure ins(var x:longint;y:longint);
begin
if x= then
begin
x:=newp(y);
exit;
end;
if y<a[x] then
begin
ins(lef[x],y);b[x]:=b[lef[x]]+b[rig[x]]+;
if fix[lef[x]]<fix[x] then rt(x);
end
else
begin
ins(rig[x],y);b[x]:=b[lef[x]]+b[rig[x]]+;
if fix[rig[x]]<fix[x] then lt(x);
end;
end;
procedure del(var x:longint;y:longint);
begin
if x= then exit;
if a[x]=y then
begin
if lef[x]= then x:=rig[x] else
if rig[x]= then x:=lef[x] else
if fix[lef[x]]>fix[rig[x]] then
begin
lt(x);del(lef[x],y);
b[x]:=b[lef[x]]+b[rig[x]]+;
end
else
begin
rt(x);del(rig[x],y);
b[x]:=b[lef[x]]+b[rig[x]]+;
end;
end
else if y<a[x] then
begin
del(lef[x],y);
b[x]:=b[lef[x]]+b[rig[x]]+;
end
else begin
del(rig[x],y);
b[x]:=b[lef[x]]+b[rig[x]]+;
end;
end;
function getrank(x,y:longint):longint;
begin
if x= then exit();
if y>a[x] then exit(b[lef[x]]++getrank(rig[x],y)) else exit(getrank(lef[x],y));
end;
function rankget(x,y:longint):longint;
begin
if y=(b[lef[x]]+) then exit(a[x]);
if y<(b[lef[x]]+) then exit(rankget(lef[x],y)) else exit(rankget(rig[x],y--b[lef[x]]));
end;
function getpre(x,y:longint):longint;
begin
if x= then exit(-maxlongint);
if a[x]<y then exit(max(a[x],getpre(rig[x],y))) else exit(getpre(lef[x],y));
end;
function getsuc(x,y:longint):longint;
begin
if x= then exit(maxlongint);
if a[x]>y then exit(min(a[x],getsuc(lef[x],y))) else exit(getsuc(rig[x],y));
end;
begin
readln(n);tot:=;head:=;
for i:= to n do
begin
readln(j,k);
case j of
:ins(head,k);
:del(head,k);
:writeln(getrank(head,k)+);
:writeln(rankget(head,k));
:writeln(getpre(head,k));
:writeln(getsuc(head,k));
end;
end;
end.