Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #210 - QMAX3VN - Sử dụng Splay Tree để xử lí Online
Ngày: 11-05-2011
Cập nhật: 11-05-2011
Người gửi: yenthanh132
Ngôn ngữ: Pascal
Xem: 689

Điểm: 3.9/5 (11 Phiếu)


{$MODE OBJFPC}
Program QMAX3VN;
Type PNode=^TNode;
     TNode=Record
             max,size,v:Longint;
             left,right,parent:Pnode;
           End;
Const MaxC=1000000001;
Var root,NilT,t1,t2:PNode;
    sentinal:TNode;
    fi,fo:Text;
    n,i,x,y:Longint;
    q:Char;
Function NewNode(v:Longint):PNode; inline;
Var p:PNode;
Begin
  New(p);
  p^.parent:=NilT;
  p^.left:=NilT;
  p^.right:=nilT;
  p^.size:=1;
  p^.v:=v;
  p^.max:=v;
  Exit(p);
End;
 
Procedure Init;
Begin
  sentinal.max:=-MaxC;
  sentinal.size:=0;
  sentinal.v:=0;
 
  NilT:=@sentinal;
  root:=NilT;
End;
 
Procedure SetLink(x,y:PNode; inleft:Boolean); inline;
Begin
  If y<>NilT then y^.parent:=x;
  If x<>NilT then If inleft then x^.left:=y else x^.right:=y
End;
 
Function fmax(a,b:Longint):Longint; inline;
Begin If a>b then exit(a) else exit(b) End;
Function fmax3(a,b,c:Longint):Longint; inline;
Begin Exit(fmax(a,fmax(b,c))) End;
 
Procedure UpTree(x:PNode); inline;
Var y,z,branch:PNode;
Begin
  y:=x^.parent;
  z:=y^.parent;
  If x=y^.left then
    Begin
      branch:=x^.right;
      SetLink(y,branch,true);
      SetLink(x,y,false);
    End
  Else
    Begin
      branch:=x^.left;
      SetLink(y,branch,false);
      SetLink(x,y,true);
    End;
  SetLink(z,x,y=z^.left);
  If y<>NilT then With y^ do
    Begin
      size:=left^.size+right^.size+1;
      max:=fmax3(left^.max,right^.max,v);
    End;
  With x^ do
    Begin
      size:=left^.size+right^.size+1;
      max:=fmax3(left^.max,right^.max,v);
    End;
End;
 
Procedure Splay(x:PNode);inline;
Var y,z:PNode;
Begin
  Repeat
    y:=x^.parent; If y=NilT then Exit;
    z:=y^.parent;
    If z<>NilT then
      If (z^.left=y)=(y^.left=x) then UpTree(y) else UpTree(x);
    UpTree(x)
  Until False;
End;
 
Function NodeAt(p:PNode; pos:Longint):PNode; inline;
Begin
  Repeat
    If p^.left^.size+1=pos then Exit(p)
    else If pos<=p^.left^.size then p:=p^.left
    else
      Begin
        Dec(pos,p^.left^.size+1);
        p:=p^.right
      End;
  Until False;
End;
 
Procedure Insert(var root:Pnode; v,pos:Longint); inline;
Var p,x:PNode;
Begin
  x:=NewNode(v);
  If root=NilT then
    Begin
      root:=x;
      Exit;
    End;
  p:=root;
  If p^.size+1=pos then
    Begin
      While p^.right<>NilT do p:=p^.right;
      SetLink(p,x,false);
    End
  Else
    Begin
      p:=NodeAt(p,pos);
      If p^.left=NilT then Setlink(p,x,true)
      else
        Begin
          p:=p^.left;
          While p^.right<>nilT do p:=p^.right;
          SetLink(p,x,false);
        End;
    End;
  While p<>NilT do
    Begin
      Inc(p^.size);
      p:=p^.parent;
    End;
  Splay(x);
  root:=x;
End;
 
Procedure Split(p:Pnode; pos:Longint; var t1,t2:PNode); inline;
Begin
  If pos=0 then
    Begin
      t1:=NilT;
      t2:=p;
      Exit;
    End;
  If pos=p^.size then
    Begin
      t1:=p;
      t2:=NilT;
      Exit;
    End;
  t1:=NodeAt(p,pos);
  Splay(t1);
  t2:=t1^.right;
  t1^.right:=NilT;
  With t1^ do
    Begin
      size:=left^.size+1;
      max:=fmax(left^.max,v);
    End;
  t2^.parent:=NilT;
End;
 
Function Join(t1,t2:PNode):Pnode; inline;
Begin
  If t1=NilT then exit(t2);
  If t2=NilT then exit(t1);
  While t1^.right<>NilT do t1:=t1^.right;
  Splay(t1);
  SetLink(t1,t2,false);
  With t1^ do
    Begin
      size:=left^.size+right^.size+1;
      max:=fmax3(left^.max,right^.max,v);
    End;
  Exit(t1)
End;
 
BEGIN
  Init;
  Assign(fi,''); Reset(fi);
  Assign(fo,''); Rewrite(fo);
  Readln(fi,n);
  For i:=1 to n do
    Begin
      Read(fi,q);
      Readln(fi,x,y);
      If q='A' then
        Insert(root,x,y)
      Else
        Begin
          Split(root,y,root,t2);
          Split(root,x-1,root,t1);
          Writeln(fo,t1^.max);
          root:=Join(root,t1);
          root:=Join(root,t2);
        End
    End;
  Close(fi); Close(fo);
END.