ORDERSET - Order statistic set

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
const finp='';
      fout='';
      MaxQ=200000;
      MaxD=4*MaxQ;
Var A:Array[1..MaxQ] of Longint;
Var ID:Array[1..MaxQ] of Longint;
Var Oder:Array[1..MaxQ] of Char;
Var Q,N,U:Longint;
Var F:Array[1..MaxD] of Longint;
(***************************)
procedure OpenFile; inline;
begin
  assign(input,finp);reset(input);
  assign(output,fout);rewrite(output);
end;

(****************************)
  procedure CloseFile; inline;
  Begin
    Close(input);
    Close(output);
  End;
(**************************************)
  procedure QS(l,r:longint); inline;
  var i,j:longint;
      tg,k:longint;
  begin
   if l>=r then exit;
   k:=A[l+random(r-l+1)];
   i:=l;
   j:=r;
     repeat
       while (A[i]<K) do inc(i);
       while (A[j]>K) do dec(j);
       if i<=j then
          Begin
            Tg:=A[i];A[i]:=A[j];A[j]:=tg;
            Inc(i);
            Dec(j);
          End;
     until i>j;
   QS(L,j);
   QS(i,R);
  end;
(*******************************)
Procedure Init; inline;
Var j,i:Longint;
Begin
  j:=1;
  For i:=2 to Q do
      If A[i]<>A[j] Then
                     Begin
                       Inc(j);
                       A[j]:=A[i];
                     End;
  N:=j;
End;
(*******************************)
  procedure Enter; inline;
  Var i:Longint;
  Begin
     Readln(Q);
     For i:=1 to Q do
         Begin
           Readln(Oder[i],A[i]);
           ID[i]:=A[i];
         End;
     QS(1,Q);
     Init;
  End;
(*******************************)
Procedure Inc_Seq(L,R,K:Longint); inline;
Var Mid,Con:Longint;
Begin
  If (A[R]<U)Or(A[L]>U) Then Exit;
  If (L=R)Then
     Begin
        F[K]:=1; Exit;
     End;

  Mid:=(L+R) Shr 1;

  Con:=K Shl 1;

  Inc_Seq(L,Mid,Con);
  Inc_Seq(Mid+1,R,Con+1);

  F[K]:=F[Con]+F[Con+1];
End;
(*******************************)
Procedure Dec_Seq(L,R,K:Longint); inline;
Var Mid,Con:Longint;
Begin
  If (A[R]<U)Or(A[L]>U) Then Exit;
  If (L=R)Then
     Begin
        F[K]:=0; Exit;
     End;

  Mid:=(L+R)shr 1;

  Con:=K Shl 1;

  Dec_Seq(L,Mid,Con);
  Dec_Seq(Mid+1,R,Con+1);

  F[K]:=F[Con]+F[Con+1];
End;
(*******************************)
Function Find(L,R,K:Longint):Longint; inline;
Var Mid:Longint;
    Con:Longint;
Begin
  If L=R Then Exit(L);

  Mid:=(L+R) shr 1;

  Con:=K Shl 1;

  If F[Con]>=U Then Find:=Find(L,Mid,Con)
               Else
                  Begin
                    U:=U-F[Con];
                    Find:=Find(Mid+1,R,Con+1);
                  End;
End;
(*******************************)
Function Get_Seq(L,R,K:Longint):Longint; inline;
Var Mid:Longint;
    Con:Longint;
Begin
  Get_Seq:=0;
  If A[L]>=U Then Exit;
  If A[R]<U Then
     Begin
       Get_Seq:=F[K];
       Exit;
     End;

  Mid:=(L+R) shr 1;

  Con:=K Shl 1;

  Get_Seq:=Get_Seq(L,Mid,Con)+Get_Seq(Mid+1,R,Con+1);
End;
(*******************************)
procedure Solve;
Var i:Longint;
Begin
   For i:=1 to Q do
       Begin
         U:=ID[i];
         If Oder[i]='I' Then Inc_Seq(1,N,1)
         Else
         If Oder[i]='D' Then Dec_Seq(1,N,1)
         Else
         If Oder[i]='K' Then
            Begin
              If U>F[1] Then Writeln('invalid')
                   Else Writeln(A[Find(1,N,1)]);
            End
         Else Writeln(Get_Seq(1,N,1));
       End;
End;
(*******************************)
  Begin
  OpenFile;
  Enter;
  Solve;
  CloseFile;
  End.

Download