DRASHOOT - Dragon Shooting
Tác giả: ladpro98
Ngôn ngữ: C++
#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;
}