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;
}

Download