Persistent segment tree

2104 -- K-th Number
Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar.
First we discretize the integers so that there are at most 1e5 integers in range, then we maintain segment tree for count of numbers in left subrange and right subrange. If it were to ask the k-th minimum number among the whole range, we can easily come up to a solution where we query left subrange whether its count is larger than k or not, if yes goes to left, otherwise go to right subrange and ask for its ( k - lc->number_count ) -th, recursively until a visit to the exact k-th is made.
Now we consider the original problem, a common technique solving range problems is to maintain the prefix sum. If we could find some property where some function f( r ) - f( l - 1 ) can lead us to the answer of [ l, r ]... there is such property in the k-th minimum problem. Imagine the [ l, r ] 1D plane as the time axis, you can think that when some time flows ( ex. l -> l + 1 ), some event occurs ( ex. frequency of the value a[ l + 1 ] adds by 1 ), we will find that ( the events that happened in time range [ 1, r ] - the events that happened in time range [ 1, l - 1 ] = events on [ l, r ] ). Now this is what persistent data structures are invented for -- they are able to record changes happening based on some versions in the past, in both efficient time and space complexity. ( O( M lg N ) extra complexity )
Notice that there are some tricks in the struct, the static memory pool declaration, and the placement new trick. It is a well-known fact that new() for dynamic memory allocation is slow, but today I learned it is really slow, by more than 10 times. I found this because it gave me a big TLE that I did not expect.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXMEM = 2e6; // as large as possible, sometimes WA is actually an RE

struct itvt{
    static itvt mem[MAXMEM]; 
    int lb, rb, cnt;
    itvt *lc, *rc;
    itvt(): cnt(0), lc(NULL), rc(NULL){}
    itvt(int _l, int _r, int _c = 0): lb(_l), rb(_r), cnt(_c), lc(NULL), rc(NULL){}
    void pull(){ cnt = lc->cnt + rc->cnt; }
} itvt::mem[MAXMEM], *ptr = itvt::mem, *root[MAXM]; // initialization is easy: ptr = itvt::mem

itvt* build(int lb, int rb){
    if( lb == rb ) return new( ptr++ ) itvt( lb, rb );
    int mid = ( lb + rb ) / 2;
    itvt *t = new( ptr++ ) itvt( lb, rb );
    t->lc = build( lb, mid ); t->rc = build( mid + 1, rb );
    return t;
}

itvt* clone(itvt *t){
    itvt *res = new( ptr++ ) itvt();
    res->lb = t->lb, res->rb = t->rb, res->cnt = t->cnt;
    res->lc = t->lc, res->rc = t->rc;
    return res;
}

itvt* add(itvt *t, int x){
    itvt *res = clone( t );
    if( t->lb == t->rb ){
        ++res->cnt;
        return res;
    }
    int mid = ( t->lb + t->rb ) / 2;
    if( x <= mid ) res->lc = add( t->lc, x );
    else res->rc = add( t->rc, x );
    res->pull();
    return res;
}

int qryKth(itvt *tl, itvt *tr, int k){
    if( tl->lb == tl->rb ) return tl->lb; // found ya!
    int mid = ( tl->lb + tl->rb ) / 2;
    int lcnt = tr->lc->cnt - tl->lc->cnt; // how many numbers are in the left subrange when [ l, r ] ( = [ 1,r ] - [ 1, l - 1 ] )
    if( k <= lcnt ) return qryKth( tl->lc, tr->lc, k );
    return qryKth( tl->rc, tr->rc, k - lcnt );
}

int n, m;
int a[MAXN];
void read_input(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
}

void solve(){
    vector<int> vmap; // discretization
    for(int i = 1; i <= n; ++i)
        vmap.push_back( a[i] );
    sort( vmap.begin(), vmap.end() );
    vmap.resize( unique( vmap.begin(), vmap.end() ) - vmap.begin() );

    root[ 0 ] = build( 0, vmap.size() - 1 ); // empty
    for(int i = 1; i <= n; ++i){ // versions: root[ i ]: the status after [ 1, i ] events
        int x = lower_bound( vmap.begin(), vmap.end(), a[i] ) - vmap.begin();
        root[ i ] = add( root[ i - 1 ], x );
    }
    while( m-- ){
        int ql, qr, k; scanf("%d%d%d", &ql, &qr, &k);
        int id = qryKth( root[ ql - 1 ], root[ qr ], k );
        printf("%d\n", vmap[ id ]);
    }
}

int main(){
    read_input();
    solve();
    return 0;
}