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.