segment-tree-persistente

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> ii;
 
struct node {
    int v;
    node *l, *r;
    node(int _v, node *_l, node *_r) : v(_v), l(_l), r(_r) { }
};
 
const int MAXN =1e5+5;
 
int N, Q, A[MAXN];
ii v[MAXN];
node* ver[MAXN];
int l, r, k;
 
node* build_pst(int L, int R) {
    if(L == R) return new node(0, NULL, NULL);
    int mid = (L+R)/2;
    return new node(0, build_pst(L, mid), build_pst(mid+1, R));
}
 
node* update_pst(node *prev, int L, int R, int p, int v) {
    if(L == R) return new node(v, NULL, NULL);
    int mid = (L+R)/2;
    node *n = new node(0, prev->l, prev->r);
    if(p <= mid) n->l = update_pst(prev->l, L, mid, p, v);
    else n->r = update_pst(prev->r, mid+1, R, p, v);
    n->v = n->l->v + n->r->v;
    return n;
}
 
int kth_pst(node *bef, node *af, int L, int R, int k) {
    if(L == R) return L;
    int a = af->l->v - bef->l->v;
    int mid = (L+R)/2;
    if(k<=a) return kth_pst(bef->l, af->l, L, mid, k);
    return kth_pst(bef->r, af->r, mid+1, R, k-a);
}
 
int main() {
    scanf("%d%d", &N, &Q);
    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        v[i] = ii(A[i], i);
    }
    sort(v, v+N);
    for(int i = 0; i < N; i++) A[v[i].second] = i;
 
    ver[0]=build_pst(0, N-1);
    for(int i = 0; i < N; i++) ver[i+1] = update_pst(ver[i], 0, N-1, A[i], 1);
    for(int i = 0; i < Q; i++) {
        scanf("%d%d%d", &l, &r, &k);
        int a = kth_pst(ver[l-1], ver[r], 0, N-1, k);
        printf("%d\n", v[a].first);
    }
}