【題解】POJ 2104 K-th Number

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, a[100005], cnt, root[100005];
vector <int> v;

struct node{
    int val;
    int r;
    int l;
    node(){
        val = r = l = 0;
    }
}T[100005*40];

int get_id(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
void update(int &x, int pre, int l, int r, int u){
    cnt++;
    x = cnt;
    T[x] = T[pre];
    T[x].val++;
    if (l == r) return;
    int mid = (l+r)/2;
    if (u <= mid){
        update(T[x].l, T[pre].l, l, mid, u);
    }
    else{
        update(T[x].r, T[pre].r, mid+1, r, u);
    }
}
int query(int x, int y, int l, int r, int k){
    //cout << l << " " << r << " " << k << " " << T[T[y].l].val << " " << T[T[x].l].val << endl;
    if (l == r) return v[l-1];
    int mid = (l+r)/2;
    if (k <= T[T[y].l].val-T[T[x].l].val){
        return query(T[x].l, T[y].l, l, mid, k);
    }
    return query(T[x].r, T[y].r, mid+1, r, k-(T[T[y].l].val-T[T[x].l].val));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++){
        update(root[i], root[i-1], 1, v.size(), get_id(a[i]));
    }
    int x, y, k;
    for (int i = 0; i < m; i++){
        cin >> x >> y >> k;
        cout << query(root[x-1], root[y], 1, v.size(), k) << "\n";
    }
}