整体二分初步

先挖个坑再说

以下是静态区间第 \(k\) 大的板子：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int n, m;

struct Que {
    int x, l, r, k;
}Q[N], L[N], R[N];
int ans[N], a[N], b[N], cnt, lsh[N];

map <int, int> mp;

struct BIT {
    int c[N];
    inline void update(int x, int v) {
        for(int i = x; i <= n; i += i & -i) c[i] += v;
    }
    inline int query(int x) {
        int ret = 0;
        for(int i = x; i; i -= i & -i) ret += c[i];
        return ret;
    }
}T;

#if 0
void solve(int ql, int qr, int l, int r) {
    if(l == r) {
        for(int i = ql; i <= qr; ++i) if(Q[i].x) ans[Q[i].x] = l;
        return;
    }
    int mid = l + r >> 1, cntl = 0, cntr = 0;
    for(int i = ql; i <= qr; ++i) {
        if(!Q[i].x)
            if(Q[i].k <= mid) L[++cntl] = Q[i], T.update(Q[i].l, 1);
            else R[++cntr] = Q[i];
        else {
            auto tmp = T.query(Q[i].r) - T.query(Q[i].l - 1);
            if(tmp < Q[i].k) Q[i].k -= tmp, R[++cntr] = Q[i];
            else L[++cntl] = Q[i];
        }
    }
    for(int i = 1; i <= cntl; ++i) {
        Q[ql + i - 1] = L[i];
        if(!L[i].x) T.update(L[i].l, -1);
    }
    for(int i = 1; i <= cntr; ++i) 
        Q[qr + i + cntl - 1] = R[i]; // 这儿锅了
    solve(ql, ql + cntl - 1, l, mid), solve(ql + cntl, qr, mid + 1, r);
}
#endif

void solve(int ql, int qr, int l, int r) {
    if(l == r) {
        for(int i = ql; i <= qr; ++i) if(Q[i].x) ans[Q[i].x] = l;
        return;
    }
    int mid = l + r >> 1, cntl = 0, cntr = 0, tmp;
    for(int i = ql; i <= qr; ++i) {
        if(!Q[i].x) {
            if(Q[i].k <= mid) L[++cntl] = Q[i], T.update(Q[i].l, 1);
            else R[++cntr] = Q[i];
        }
        else {
            tmp = T.query(Q[i].r) - T.query(Q[i].l - 1);
            if(tmp < Q[i].k) Q[i].k -= tmp, R[++cntr] = Q[i];
            else L[++cntl] = Q[i];
        }
    }
    for(int i = 1; i <= cntl; ++i) {
        Q[ql - 1 + i] = L[i];
        if(!L[i].x) T.update(L[i].l, -1);
    }
    for(int i = 1; i <= cntr; ++i) 
        Q[ql - 1 + cntl + i] = R[i];
    solve(ql, ql + cntl - 1, l, mid), solve(ql + cntl, qr, mid + 1, r);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", b + i), Q[i] = {0, i, i, b[i]};
    sort(b + 1, b + n + 1);
    mp[b[1]] = ++cnt, lsh[cnt] = b[1];
    for(int i = 2; i <= n; ++i) if(b[i] != b[i - 1]) mp[b[i]] = ++cnt, lsh[cnt] = b[i];
    int l, r, k;
    for(int i = 1; i <= m; ++i) scanf("%d %d %d", &l, &r, &k), Q[n + i] = {i, l, r, k};
    for(int i = 1; i <= n; ++i) Q[i].k = mp[Q[i].k];
    solve(1, n + m, 1, cnt);
    for(int i = 1; i <= m; ++i) printf("%d\n", lsh[ans[i]]);
    return 0;
}