1225spl.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

//Splay tree, TLE
{$Q-,R-}
program tju1225;
const
  maxn=100000;
var
  val,size,lchild,rchild,parent,free:array[0..maxn]of longint;
  freep,n,limit,delta{real minus stored},i,k,leave:longint;
  c:char;
procedure zig(a:longint);
  var
    f,b,c,s:longint;
  begin
    f:=parent[a];b:=lchild[a];c:=rchild[b];
    if val[a]<val[f] then lchild[f]:=b else rchild[f]:=b;
    lchild[a]:=c;rchild[b]:=a;
    parent[a]:=b;parent[b]:=f;parent[c]:=a;
    s:=size[a]-size[b]+size[c];size[b]:=size[a];size[a]:=s;
  end;
procedure zag(a:longint);
  var
    f,b,c,s:longint;
  begin
    f:=parent[a];b:=rchild[a];c:=lchild[b];
    if val[a]<val[f] then lchild[f]:=b else rchild[f]:=b;
    rchild[a]:=c;lchild[b]:=a;
    parent[a]:=b;parent[b]:=f;parent[c]:=a;
    s:=size[a]-size[b]+size[c];size[b]:=size[a];size[a]:=s;
  end;
procedure splay(p:longint);
  var
    f:longint;
  begin
    while p<>lchild[0] do begin
      f:=parent[p];
      if val[p]<val[f] then begin
        if (f<>lchild[0]) and (val[f]<val[parent[f]]) then zig(parent[f]);
        zig(f);
      end
      else begin
        if (f<>lchild[0]) and (val[f]>val[parent[f]]) then zag(parent[f]);
        zag(f);
      end;
    end;
  end;
procedure insert(x:longint);
  var
    p:longint;
  begin
    if lchild[0]=0 then begin
      p:=free[1];inc(freep);lchild[0]:=p;
      val[p]:=x;size[p]:=1;lchild[p]:=0;rchild[p]:=0;parent[p]:=0;
      exit;
    end;
    p:=lchild[0];
    repeat
      inc(size[p]);
      if val[p]=x then break;
      if val[p]>x then
        if lchild[p]>0 then p:=lchild[p] else begin
          lchild[p]:=free[freep];inc(freep);parent[lchild[p]]:=p;p:=lchild[p];
          val[p]:=x;size[p]:=1;lchild[p]:=0;rchild[p]:=0;break;
        end
      else
        if rchild[p]>0 then p:=rchild[p] else begin
          rchild[p]:=free[freep];inc(freep);parent[rchild[p]]:=p;p:=rchild[p];
          val[p]:=x;size[p]:=1;lchild[p]:=0;rchild[p]:=0;break;
        end;
    until false;
    splay(p);
  end;
procedure recycle(p:longint);
  begin
    if p=0 then exit;
    recycle(lchild[p]);recycle(rchild[p]);
    dec(freep);free[freep]:=p;
  end;
procedure delete(x:longint);
  var
    p:longint;
  begin
    p:=lchild[0];
    while val[p]<>x do
      if val[p]>x then if lchild[p]=0 then break else p:=lchild[p]
             else if rchild[p]=0 then break else p:=rchild[p];
    splay(p);
    inc(leave,size[lchild[p]]);dec(size[p],size[lchild[p]]);
    recycle(lchild[p]);
    if val[p]<x then begin
      inc(leave,size[p]-size[rchild[p]]);
      lchild[0]:=rchild[p];parent[lchild[0]]:=0;
      dec(freep);free[freep]:=p;
    end
    else
      lchild[p]:=0;
  end;
procedure find_order(k:longint);
  var
    p:longint;
  begin
    p:=lchild[0];
    repeat
      if size[rchild[p]]>=k then
        p:=rchild[p]
      else if size[p]-size[lchild[p]]>=k then
        break
      else begin
        dec(k,size[p]-size[lchild[p]]);
        p:=lchild[p];
      end;
    until false;
//{$}write('Result: ');
    writeln(val[p]+delta);
    splay(p);
  end;
{procedure traverse(p,l:longint);
  var
    i:longint;
  begin
    if rchild[p]>0 then traverse(rchild[p],l+1);
    for i:=1 to l*3 do write(' ');
    write('[',p,']',val[p]+delta);
    i:=size[p]-size[lchild[p]]-size[rchild[p]];
    if i=1 then writeln else writeln('x',i);
    if lchild[p]>0 then traverse(lchild[p],l+1);
  end;}
begin
//{$}assign(input,'1225.in');reset(input);
//{$}assign(output,'1225.out');rewrite(output);
  val[0]:=maxlongint;for i:=1 to maxn do free[i]:=i;freep:=1;
  repeat
    readln(n,limit);delta:=0;leave:=0;lchild[0]:=0;
    for i:=1 to n do begin
      readln(c,k);
//{$}      writeln('-----Operation ',i,': ',c,' ',k,'-----');
      case c of
        'I':if k>=limit then insert(k-delta);
        'A':inc(delta,k);
        'S':if lchild[0]>0 then begin dec(delta,k);delete(limit-delta);end;
        'F':if k>size[lchild[0]] then writeln(-1) else find_order(k);
      end;
//{$}      if lchild[0]=0 then writeln('Empty') else traverse(lchild[0],0);
//{$}writeln('Leave: ',leave);
    end;
//{$}write('Leave: ');
    writeln(leave);
    recycle(lchild[0]);
  until seekeof;
//{$}close(output);
end.