整体二分模板题, 有些细节需要注意

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

#include<cstring>

using namespace std;

inline int read()

{

    int x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

void println(int x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    int ans[10 + (1 << 4)], top = 0;

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const int MAXN = (int)1e5 + (1 << 5), MAXM = (int)5e4 + (1 << 4);

const int oo = INT_MAX;

int a[MAXN];

struct query

{

    int L, R, k, ID;

    query(){}

    query(int L, int R, int k, int ID): L(L), R(R), k(k), ID(ID){}

}Q[MAXN];

int res[MAXN], sum[MAXN];

int nxt[MAXN][2], pre[MAXN][2];

int _a[MAXN], map[MAXN];

query _Q[MAXM];

int ans[MAXM];

void solve(int mn, int mx, int L, int R, int QL, int QR)

{

    if(mn >= mx)

    {

        for(int i = QL; i <=QR; i ++)

            ans[Q[i].ID] = mn;

        return;

    }

    int cur = (mn + mx) >> 1;

    for(int i = L; i <= R; i ++)

        res[i] = (a[i] <= cur);

    sum[L] = res[L];

    for(int i = L + 1; i <= R; i ++)

        sum[i] = sum[i - 1] + res[i];

    pre[L][res[L]] = L, pre[L][res[L] ^ 1] = - oo;

    for(int i = L + 1; i <= R; i ++)

        pre[i][res[i]] = i, pre[i][res[i] ^ 1] = pre[i - 1][res[i] ^ 1];

    nxt[R][res[R]] = R, nxt[R][res[R] ^ 1] = oo;

    for(int i = R - 1; i >= L; i --)

        nxt[i][res[i]] = i, nxt[i][res[i] ^ 1] = nxt[i + 1][res[i] ^ 1];

    int Ltop = L, Rtop = R;

    for(int i = L; i <= R; i ++)

    {

        if(res[i])

            _a[Rtop] = a[i], map[i] = Rtop --;

        else

            _a[Ltop] = a[i], map[i] = Ltop ++;

    }

    int mid = Rtop;

    for(int i = L; i <= R; i ++)

        a[i] = _a[i];

    Ltop = QL, Rtop = QR;

    for(int i = QL; i <= QR; i ++)

    {

        int cnt = sum[Q[i].R] - sum[Q[i].L - 1];

        if(cnt < Q[i].k)

        {

            Q[i].L = map[nxt[Q[i].L][0]];

            Q[i].R = map[pre[Q[i].R][0]];

            Q[i].k -= cnt;  //当 cnt < k 时要在k中减去cnt

            if(Q[i].L > Q[i].R)

                swap(Q[i].L, Q[i].R); //记得要判断是否需要调换顺序

            _Q[Ltop ++] = Q[i];

        }

        else if (cnt >= Q[i].k) //当 cnt >= k时则不需要减去cnt

        {

            Q[i].L = map[nxt[Q[i].L][1]];

            Q[i].R = map[pre[Q[i].R][1]];

            if(Q[i].L > Q[i].R)

                swap(Q[i].L, Q[i].R);

            _Q[Rtop --] = Q[i];

        }

    }

    for(int i = QL; i <= QR; i ++)

        Q[i] = _Q[i];

    for(int i = L;  i <= R; i ++)

        sum[i] = 0;

    solve(cur + 1, mx, L, mid, QL, Rtop);

    solve(mn, cur, mid + 1, R, Ltop, QR);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("POJ2104.in", "r", stdin);

    freopen("POJ2104.out", "w", stdout);

    #endif

    int n = read();

    int m = read();

    int mx = - oo, mn = oo;

    for(int i = 1; i <= n; i ++)

        a[i] = read(), mx = max(mx, a[i]), mn = min(mn, a[i]);

    for(int i = 1; i <= m; i ++)

    {

        int L = read(), R = read(), k = read();

        Q[i] = query(L, R, k, i);

    }

    memset(sum, 0, sizeof(sum));

    solve(mn, mx, 1, n, 1, m);

    for(int i = 1; i <= m; i ++)

        println(ans[i]);

}