DRASHOOT - Dragon Shooting

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
  SNODE         =       262144;

var
  f1,f2         :       text;
  n,m           :       longint;
  a             :       array[1..MAXN] of longint;
  sl,ln         :       array[1..snode] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        read(f1,a[i]);
    end;

procedure init(i,l,r:longint); inline;
    var
      mid:longint;
    begin
      if l=r then
        begin
          ln[i]:=a[l];
          exit;
        end;
      mid:=(l+r) shr 1;
      init(i shl 1,l,mid);
      init(i shl 1+1,mid+1,r);
      ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
    end;

function kth(u,i,l,r:longint):longint; inline;
    var
      mid:longint;
    begin
      if sl[i]=0 then
        if u<=r-l+1 then exit(l+u-1);
      mid:=(l+r) shr 1;
      if (mid-l+1-sl[i shl 1]) >= u then exit(kth(u,i shl 1,l,mid))
      else exit(kth(u-(mid-l+1-sl[i shl 1]),i shl 1+1,mid+1,r));
    end;

procedure erase(u,i,l,r:longint); inline;
    var
      mid:longint;
    begin
      if (u<l) or (r<u) then exit;
      if l=r then
        begin
          ln[i]:=-1;
          sl[i]:=1;
          exit;
        end;
      inc(sl[i]);
      mid:=(l+r) shr 1;
      erase(u,i shl 1,l,mid);
      erase(u,i shl 1+1,mid+1,r);
      ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
    end;

function get(u,i,l,r:longint):longint; inline;
    var
      mid:longint;
    begin
      if l=r then exit(l);
      mid:=(l+r) shr 1;
      if sl[i shl 1]>=u then exit(get(u,i shl 1,l,mid))
      else exit(get(u-sl[i shl 1],i shl 1+1,mid+1,r));
    end;

function getMax(u,v,i,l,r:longint):longint;
    var
      mid:longint;
    begin
      if (v<l) or (r<u) then exit(0);
      if (u<=l) and (r<=v) then exit(ln[i]);
      mid:=(l+r) shr 1;
      exit(max(getMax(u,v,i shl 1,l,mid),getMax(u,v,i shl 1+1,mid+1,r)));
    end;

procedure solve;
    var
      i,u,v:longint;
      c:char;
    begin
      inc(n);
      erase(n,1,1,n);
      init(1,1,n);
      readln(f1,m);
      for i:=1 to m do
        begin
          read(f1,c);
          if c='Q' then
            begin
              readln(f1,u,v);
              u:=get(u,1,1,n);
              v:=get(v+1,1,1,n)-1;
              v:=getMax(u,v,1,1,n);
              if v<=0 then writeln(f2,'NONE')
              else writeln(f2,v);
            end
          else //c='S'
            begin
              readln(f1,u);
              u:=kth(u,1,1,n);
              erase(u,1,1,n);
            end;
        end;
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Download