sbt:

1503: [NOI2004]郁闷的出纳员

 [toggle Title="code "][pascal]varl,r,a,size:Array[1..100000]of longint;le:Array[1..100000]of boolean;ans:int64;root,nn,n,m,i,k,j:longint;c,space:char;procedure lr(var x:longint);var k:longint;begink:=r[x]; r[x]:=l[k] ; l[k]:=x;size[k]:=size[x];size[x]:=size[l[x]]+size[r[x]]+1;x:=k;end;procedure rr(var x:longint);var k:longint;begink:=l[x];l[x]:=r[k];r[k]:=x;size[k]:=size[x];size[x]:=size[l[x]]+size[r[x]]+1;x:=k;end;procedure maint(var x:longint; f:boolean);beginif f thenif size[r[r[x]]]>size[l[x]] thenlr(x)else if size[l[r[x]]]>size[l[x]] thenbeginrr(r[x]);lr(x);end else exitelseif size[l[l[x]]]>size[r[x]] thenrr(x)else if size[r[l[x]]]>size[r[x]] thenbeginlr(l[x]);rr(x);end else exit;maint(l[x],false);maint(r[x],true);maint(x,true);maint(x,false);end;function new(x:longint):longint;begininc(nn);  size[nn]:=1;a[nn]:=x;  exit(nn) ;end;procedure insert(var t,x:longint);var k:longint;beginif t=0 thenbegin t:=new(x); exit; end;inc(size[t]);if x<a[t] then insert(l[t],x) else insert(r[t],x);if x<>a[t] then maint(t,x>a[t]);end;function delete(var t:longint;x:longint):longint;var rr,k:longint;begindec(size[t]);if (x=a[t])or((x<a[t])and(l[t]=0))or((x>a[t])and(r[t]=0)) thenbeginrr:=a[t];if (l[t]=0)or(r[t]=0) thent:=l[t]+r[t]else a[t]:=delete(l[t],a[t]+1);exit(rr);endelse if a[t]>x then  exit(delete(l[t],x))else exit(delete(r[t],x));end;function select(t,x:longint):longint;var i:longint;beginif x>size[t] then exit(0);i:=t;while true dobeginif size[l[i]]+1=x then exit(i);if size[l[i]]+1>x then i:=l[i]elsebeginx:=x-size[l[i]]-1;i:=r[i];end;end;end;beginreadln(n,m);for i:=1 to n dobeginreadln(c,space,k);if c='I' thenbeginif k<m thenelse insert(root,k);end;if c='F' thenif nn-ans<k then writeln(-1)else writeln(a[select(root,(nn-ans)-k+1)]);if c='A' thenfor j:=1 to nn doa[j]:=a[j]+k;if c='S' thenbeginfor j:=1 to nn doa[j]:=a[j]-k;for j:=1 to nn doif (a[j]<m)and(le[j]=false) thenbegininc(ans);delete(root,a[j]);le[j]:=true;end;end;end;writeln(ans);end.[/pascal][/toggle]  [toggle Title="cod