【題解】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";
}
}
```