7469번: K번째 숫자

https://www.acmicpc.net/problem/7469

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m;
vector<int> v[MXN * 4];
void insert(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l^r) {
        insert(h * 2 + 1, l, (l + r) / 2, g, x);
        insert(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    }
    v[h].push_back(x);
}
int query(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return 0;
    if (gl <= l && r <= gr) return upper_bound(v[h].begin(), v[h].end(), x) - v[h].begin();
    return query(h * 2 + 1, l, (l + r) / 2, gl, gr, x) + query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(0, 1, n, i, x);
    for (int i = 0; i < n * 4; i++) sort(v[i].begin(), v[i].end());
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        int l = -1e9, r = 1e9, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (query(0, 1, n, x, y, mid) < z) l = mid + 1;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}