照着OIwiki打的

#include <bits/stdc++.h>
using namespace std;
struct Number {int index, data;};
struct Query {int left, right, k, id;};
vector<Number> arr;
vector<Query> querys;
int tree[200005], ans[200005], n, m;
inline int lowbit(int x) {return x & (-x);}
void add(int x, int y) {for(; x <= n; x += lowbit(x)) tree[x] += y;}
int ask(int x) {int ret = 0; for(; x > 0; x -= lowbit(x)) ret += tree[x]; return ret;}
void solve(int l, int r, vector<Number> a, vector<Query> q){
    printf("%d %d\n", l, r);
    int mid = (l + r) / 2;
    if(a.size() == 1 && q.size() == 1) return;
    if(l == r){
        for(int i = 1; i < q.size(); i++)
            ans[q[i].id] = l;
        return;
    }
    vector<Number> leftA, rightA;
    vector<Query> leftQ, rightQ;
    leftA.push_back(Number()), rightA.push_back(Number());
    leftQ.push_back(Query()), rightQ.push_back(Query());
    for(int i = 1; i < a.size(); i++){
        if(a[i].data <= mid) leftA.push_back(a[i]), add(a[i].index, 1);
        else rightA.push_back(a[i]);
    }
    for(int i = 1; i < q.size(); i++){
        int t = ask(q[i].right) - ask(q[i].left - 1);
        if(q[i].k <= t) leftQ.push_back(q[i]);
        else q[i].k -= t, rightQ.push_back(q[i]);
    }
    for(int i = 1; i < a.size(); i++) add(a[i].index, -1);
    solve(l, mid, leftA, leftQ), solve(mid + 1, r, rightA, rightQ);
    return;
}
int main(){
    int mn = INT_MAX, mx = INT_MIN;
    scanf("%d %d", &n, &m);
    arr.resize(n + 1), querys.resize(m + 1);
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i].data), arr[i].index = i, mn = min(mn, arr[i].data), mx = max(mx, arr[i].data);
    for(int i = 1; i <= m; i++)
        scanf("%d %d %d", &querys[i].left, &querys[i].right, &querys[i].k), querys[i].id = i;
    solve(mn, mx, arr, querys);
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[querys[i].id]);
    return 0;
}