算法

(整体二分，树状数组) $O(n \log^2 n)$

1. 换一个角度思考问题。将数组从小到大排序，同时记录每个值原来的下标。例如样例排完序后的二元组就是 (1, 1), (2, 3), (3, 5), (4, 7), (5, 2), (6, 4), (7, 6)。二元组第一个数字为数值，第二个数字为原来的下标。
2. 考虑一个询问 [q.l, q.r, q.k]，我们进行二分答案然后判定。假设当前的二分区间为 [L, R]，二分某个位置 mid，我们可以在线性时间内统计数组 [L, mid] 中，有多少个数字的原下标位于区间 [q.l, q.r] 中，不妨记为 t。如果 q.k <= t ，则需要继续二分区间 [L, mid]。否则，q.k -= t，然后二分区间 [mid + 1, R]。
3. 对于多个询问，同样可以采取这样的策略。我们在二分的过程中，将被询问区间分成两类，一类继续二分左区间，一类继续二分右区间。这里需要注意的是，我们不能使用普通前缀和数组进行统计（即扫一遍 1 到 n 求前缀和），而是使用树状数组动态维护前缀和。具体得，每次二分时，扫描区间 [L, mid] 的所有数字，对每个数字的原下标 x，在树状数组上 update(x, 1)。对于集合 [l, r] 内的每个询问，求 query(q[i].r) - query(q[i].l - 1) 记为 t，然后根据 t 和 k 的关系将区间分为两类，然后继续递归求解两个区间。
4. 递归函数中大写的 L, R 表示排序后数组上的区间，l, r 表示询问集合的区间。q[i].l, q[i].r 表示第 i 个询问的区间。

时间复杂度

• 不妨假设询问和数组长度同阶，则递归表达式为 $T(n) = 2T(n / 2) + O(n \log n)$，故时间复杂度为 $O(n \log^2 n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 50010;

int n, m;

struct A {
    int id, x;
}a[N];

struct Q {
    int id;
    int l, r, k;
}q[M];

int f[N], ans[M];

inline bool cmp(const A &p, const A &q) {
    return p.x < q.x;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += f[x];

    return res;
}

inline void update(int x, int y) {
    for (; x <= n; x += x & -x)
        f[x] += y;
}

void solve(int L, int R, int l, int r) {
    if (l > r)
        return;

    if (L == R) {
        for (int i = l; i <= r; i++)
            ans[q[i].id] = a[L].x;
        return;
    }

    int mid = (L + R) >> 1;

    for (int i = L; i <= mid; i++)
        update(a[i].id, 1);

    int i = l, j = r, t;

    while (i <= j) {
        while (i <= j && q[i].k <= query(q[i].r) - query(q[i].l - 1))
            i++;

        while (i <= j && q[j].k > (t = query(q[j].r) - query(q[j].l - 1))) {
            q[j].k -= t;
            j--;
        }

        if (i < j)
            swap(q[i], q[j]);
    }

    for (int i = L; i <= mid; i++)
        update(a[i].id, -1);

    solve(L, mid, l, j);
    solve(mid + 1, R, i, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }

    for (int i = 1; i <= m; i++) {
        q[i].id = i;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
    }

    sort(a + 1, a + 1 + n, cmp);

    solve(1, n, 1, m);

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}