DRASHOOT - Dragon Shooting
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const fi='';
maxn=100010;
oo=1000000;
var n,m:longint;
a,h,f,g:array[1..maxn shl 2] of longint;
pos,d:array[1..maxn] of longint;
procedure add(node,l,r,x,val:longint);
var mid:longint;
begin
if (l=x) and (r=x) then
begin
a[node]:=val; h[node]:=x; pos[x]:=node;
end
else
begin
mid:=(l+r) shr 1;
if x<=mid then add(node shl 1,l,mid,x,val)
else add(node shl 1+1,mid+1,r,x,val);
if val>a[node] then a[node]:=val;
h[node]:=h[node shl 1];
end;
end;
procedure rf;
var i,x:longint;
begin
read(n);
for i:=1 to n do
begin
read(x);
add(1,1,n,i,x);
end;
end;
function find(node,l,r,val:longint):longint;
var mid:longint;
begin
if l=r then find:=l
else
begin
mid:=(l+r) shr 1;
val:=val+g[node];
if h[node shl 1+1]<=val then
find:=find(node shl 1+1,mid+1,r,val)
else
find:=find(node shl 1,l,mid,val);
end;
end;
procedure update(node,l,r,x:longint);
var mid:longint;
begin
end;
procedure incr(node,l,r,x,y:longint);
var mid:longint;
begin
if (l=x) and (r=y) then
begin
f[node]:=f[node]+1;
g[node]:=g[node]+1;
h[node]:=h[node]-1;
end
else
begin
mid:=(l+r) shr 1;
if x<=mid then incr(node shl 1,l,mid,x,min(y,mid));
if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y);
f[node]:=max(f[node shl 1],f[node shl 1+1])+g[node];
end;
end;
procedure update(x:longint);
begin
while x>1 do
begin
x:=x shr 1;
a[x]:=max(a[x shl 1],a[x shl 1+1]);
h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x];
end;
end;
function find2(node,l,r,val:longint):longint;
var mid:longint;
begin
if (l=r) then find2:=l
else
begin
mid:=(l+r) shr 1;
val:=val-g[node];
if f[node shl 1]>=val then
find2:=find2(node shl 1,l,mid,val)
else find2:=find2(node shl 1+1,mid+1,r,val);
end;
end;
procedure get(node,l,r,x,y:longint;var s:longint);
var mid,t,u:longint;
begin
if (l=x) and (r=y) then s:=a[node]
else
begin
mid:=(l+r) shr 1;
t:=-1; u:=-1;
if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t);
if y>mid then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u);
s:=max(t,u);
end;
end;
procedure pr;
var i,x,y,t,u,dem,re:longint; c:char;
begin
readln(m); dem:=0;
for i:=1 to m do
begin
read(c);
if c='S' then
begin
readln(x);
y:=find(1,1,n,x);
a[pos[y]]:=-1; h[pos[y]]:=oo;
if y<n then incr(1,1,n,y+1,n);
update(pos[y]);
dem:=dem+1;
end
else
begin
re:=-1;
readln(x,y);
if x>dem then
begin
writeln('NONE'); continue;
end;
t:=find2(1,1,n,x);
if y>=dem then u:=n
else u:=find2(1,1,n,y+1)-1;
get(1,1,n,t,u,re);
if re=-1 then writeln('NONE') else writeln(re);
end;
end;
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.