data-structure - Persistance Segment Tree (kthNUM)

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int L[N*20], R[N*20], V[N*20];

int sz = 0;
int a[N];
int root[N];

void build(int &n,int b,int e)
{
    n = ++sz;
    V[n] = 0;
    if(b==e) return;
    int mid = (b+e)/2;
    build(L[n],b,mid);
    build(R[n],mid+1,e);
}

void update(int &n,int pre,int b,int e,int v)
{
    n = ++sz;
    L[n] = L[pre],R[n] = R[pre],V[n] = V[pre];

    if(b==e && b == v ) {
        V[n] ++;
        return;
    }
    int mid = (b+e)/2;
    if(v <= mid ) update(L[n], L[pre], b,mid, v);
    else update(R[n], R[pre], mid+1,e, v);
    V[n] = V[L[n]] + V[R[n]];
}

int query(int r1,int r2,int b,int e,int k)
{
    if(b==e) return b;
    int oo = V[L[r1]] - V[L[r2]];

    int mid = (b+e)/2;

    if(oo >= k ) return query(L[r1], L[r2],  b, mid, k);
    else return query(R[r1], R[r2], mid+1,e, k - oo );
}
int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    vector<int>ar;

    for(int i = 1; i <= n; i ++ ) {
        scanf("%d",&a[i]);
        ar.push_back(a[i]);
    }
    sort(ar.begin() , ar.end());
    ar.resize(unique(ar.begin() , ar.end()) - ar.begin()) ;
    int SZ = (int)ar.size()-1;
    build(root[0],0,SZ);
    for(int i = 1; i <= n; i ++) {
        int val = lower_bound(ar.begin() , ar.end(), a[i]) - ar.begin();
        update(root[i] , root[i-1] , 0,SZ , val);
    }
    while(q--) {
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        int v = query(root[r], root[l-1], 0,SZ , k);
        printf("%d\n",ar[v]);
    }
}