## Editorial for Dragon Shooting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

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.


#### Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;
int MAX[4 * N], sz[4 * N], a[N];
int n, m;

#define idL (id << 1)
#define idR (idL | 1)
struct node {
int l, r, id;
node (int _l, int _r, int _id): l(_l), r(_r), id(_id) {}
node left()
{return node(l, l + r >> 1, idL);}
node right()
{return node((l + r >> 1) + 1, r, idR);}

void build() {
if (l > r) return;
if (l == r) {
sz[id] = 1; MAX[id] = a[l];
return;
}
left().build(); right().build();
sz[id] = r - l + 1;
MAX[id] = max(MAX[idL], MAX[idR]);
}

int erase(int i) {
if (l == r) {
MAX[id] = -1; sz[id] = 0;
return l;
}
int pos;
if (sz[idL] >= i)
pos = left().erase(i);
else
pos = right().erase(i - sz[idL]);
sz[id]--; MAX[id] = max(MAX[idL], MAX[idR]);
return pos;
}

int getMax(int i, int j) {
if (l > r || r < i || j < l) return -1;
if (i <= l && r <= j) return MAX[id];
return max(left().getMax(i, j), right().getMax(i, j));
}
};

struct fenwickTree {
int bit[N];
void Upd(int i) {for(; i < N; i += i & -i) bit[i]++;}
int Get(int i) {
int s = 0;
for(; i; i -= i & -i) s += bit[i];
return s;
}
} BIT;

int bsL(int x) {
int l = 1, r = n, k = -1;
while (l <= r) {
int m = l + r >> 1;
if (BIT.Get(m) >= x) {
k = m; r = m - 1;
}
else l = m + 1;
}
return k;
}

int bsR(int x) {
int l = 1, r = n, k = -1;
while (l <= r) {
int m = l + r >> 1;
if (BIT.Get(m) <= x) {
k = m; l = m + 1;
}
else
r = m - 1;
}
return k;
}

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
node root (1, n, 1);
REP(i, 1, n) cin >> a[i];
root.build();
int ans, pos, x, y, q; char ch;
cin >> q;
while (q--) {
cin >> ch;
if (ch == 'S') {
cin >> pos;
pos = root.erase(pos);
BIT.Upd(pos);
}
else {
cin >> x >> y;
if (x < 0) x = 0;
if (y > n) y = n;
x = bsL(x); y = bsR(y);
if (x < 0 || y < 0) ans = -1;
else
ans = root.getMax(x, y);
if (ans == -1) cout << "NONE\n";
else cout << ans << '\n';
}
}
return 0;
}


#### Code mẫu của RR

//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.


## Comments

Please read the guidelines before commenting.

There are no comments at the moment.