学步园

我的第一颗BST！！！

用了splay

code：

type
tree=record
l,r,f,v,size:longint;
end;
var
t:array[0..100005] of tree;
root,r,n,min,i,k,add,zzn,num:longint;
ch:char;
 
procedure left(p:longint);
var gp,f,ll:longint;
begin
f:=t[p].f;
t[f].size:=t[f].size-t[t[p].r].size-1;
t[p].size:=t[p].size+t[t[f].l].size+1;
 
ll:=t[p].l;
t[ll].f:=f;
t[f].r:=ll;
 
gp:=t[f].f;
if t[gp].l=f then
  t[gp].l:=p
else t[gp].r:=p;
t[p].f:=gp;
 
t[f].f:=p;
t[p].l:=f;
end;
 
procedure right(p:longint);
var gp,f,rr:longint;
begin
f:=t[p].f;
t[f].size:=t[f].size-t[t[p].l].size-1;
t[p].size:=t[p].size+t[t[f].r].size+1;
 
rr:=t[p].r;
t[rr].f:=f;
t[f].l:=rr;
 
gp:=t[f].f;
if t[gp].l=f then
  t[gp].l:=p
else t[gp].r:=p;
t[p].f:=gp;
 
t[f].f:=p;
t[p].r:=f;
end;
 
procedure splay(x:longint);
var p:longint;
begin
while t[x].f<>root do
begin
  p:=t[x].f;
  if t[p].f=root then
  begin
    if x=t[p].l then
      right(x)
    else left(x);
    break;
  end;
  if x=t[p].l then
  begin
    if p=t[t[p].f].l then
    begin
      right(p);
      right(x);
    end
    else
    begin
      right(x);
      left(x);
    end;
  end
  else
  begin
    if p=t[t[p].f].r then
    begin
      left(p);
      left(x);
    end
    else
    begin
      left(x);
      right(x);
    end;
  end;
end;
end;
 
procedure insert(p,x:longint);
begin
inc(t[p].size);
if x<=t[p].v then
begin
  if t[p].l=0 then
  begin
    inc(zzn);
    t[p].l:=zzn;
    t[zzn].v:=x;
    t[zzn].f:=p;
    t[zzn].size:=1;
    t[zzn].l:=0;
    t[zzn].r:=0;
  end
  else insert(t[p].l,x);
end
else begin
  if t[p].r=0 then
  begin
    inc(zzn);
    t[p].r:=zzn;
    t[zzn].v:=x;
    t[zzn].f:=p;
    t[zzn].size:=1;
    t[zzn].l:=0;
    t[zzn].r:=0;
  end
  else insert(t[p].r,x);
end;
end;
 
function del(p:longint):longint;
begin
if p=0 then
  exit(0);
del:=0;
if t[p].v+add>=min then
begin
  del:=del(t[p].l);
  t[p].size:=t[p].size-del;
end
else
begin
  if p=root then
  begin
    root:=t[p].r;
    del(root);
  end
  else
  begin
  if t[t[p].f].l=p then
  begin
    del:=t[t[p].l].size+1;
    t[t[p].f].l:=t[p].r;
    t[t[p].r].f:=t[p].f;
    del:=del+del(t[p].r);
  end
  else
  begin
    del:=t[t[p].l].size+1;
    t[t[p].f].r:=t[p].r;
    t[t[p].r].f:=t[p].f;
    del:=del+del(t[p].r);
  end;
  end;
end;
end;
 
function rank(p,x:longint):longint;
begin
if t[t[p].r].size=x-1 then
  exit(p);
if x<=t[t[p].r].size then
  exit(rank(t[p].r,x));
rank:=rank(t[p].l,x-t[t[p].r].size-1);
end;
 
begin
randomize;
readln(n,min);
for i:=1 to n do
begin
  readln(ch,k);
  if ch='I' then
    if k>=min then
    begin
      if root=0 then
      begin
        root:=1;
        t[1].v:=k-add;
        t[1].l:=0;
        t[1].r:=0;
        t[1].f:=0;
        t[1].size:=1;
        num:=num+1;
        zzn:=1;
      end
      else
      begin
        insert(root,k-add);
        num:=num+1;
        splay(zzn);
      end;
    end;
  if ch='A' then
    add:=add+k;
  if ch='S' then
  begin
    add:=add-k;
    del(root);
  end;
  if ch='F' then
  begin
    if k>t[root].size then
      writeln(-1)
    else
    begin
      r:=rank(root,k);
      writeln(t[r].v+add);
      if r<>root then
        splay(r);
    end;
  end;
end;
write(num-t[root].size);
end.