前置知识：分治，二分。
整体二分
整体二分，顾名思义就是将很多询问同时进行二分。
具体来说，设函数 为现在正在处理询问序列 里的询问，答案值域为 。
-
如果 为空，直接返回。
-
如果 ，将 里的每一个询问的答案都赋为 （或 ），然后返回。
-
设 ，对于 里的每一个询问，根据 的结果，来将 分为两个集合 与 。
-
递归处理 与 。
模板题代码：
#include <algorithm>
#include <cstdio>
inline int lowbit(int x){return x & -x;}
struct que{
int op, l, r, k, id;
}q[400001], lq[400001], rq[400001];
int l, tr[200001];
void add(int p, int x){
while (p <= l) tr[p] += x, p += lowbit(p);
}
int query(int p){
int ans = 0;
while (p) ans += tr[p], p -= lowbit(p);
return ans;
}
using namespace std;
int n, m, a[200001], _, b[200001], ans[200001];
void solve(int l, int r, int L, int R){
if (l > r) return;
if (L == R){
for (int i = l;i <= r;i ++){
if (q[i].op == 2) ans[q[i].id] = L;
}
return;
}
int mid = L + R >> 1, lt = 0, rt = 0;
for (int i = l;i <= r;i ++){
if (q[i].op == 1){
if (q[i].r <= mid) add(q[i].k, 1), lq[++ lt] = q[i];
else rq[++ rt] = q[i];
}
else {
int cnt = query(q[i].r) - query(q[i].l - 1);
if (q[i].k <= cnt) lq[++ lt] = q[i];
else rq[++ rt] = q[i], rq[rt].k -= cnt;
}
}
for (int i = l;i <= r;i ++){
if (q[i].op == 1 && q[i].r <= mid) add(q[i].k, -1);
}
for (int i = 1;i <= lt;i ++) q[l + i - 1] = lq[i];
for (int i = 1;i <= rt;i ++) q[l + lt + i - 1] = rq[i];
solve(l, l + lt - 1, L, mid), solve(l + lt, r, mid + 1, R);
}
int main(){
scanf("%d%d", &n, &m), l = n, m += n;
for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[++ _] = a[i];
sort(b + 1, b + _ + 1);
_ = unique(b + 1, b + _ + 1) - b - 1;
for (int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1, b + _ + 1, a[i]) - b;
for (int i = 1;i <= n;i ++) q[i].r = a[i], q[i].k = i, q[i].op = 1, q[i].id = 0;
for (int i = n + 1;i <= m;i ++) q[i].op = 2, scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k), q[i].id = i - n;
solve(1, m, 1, _);
for (int i = 1;i <= m - n;i ++) printf("%d\n", b[ans[i]]);
}