Persistent segment tree

/*
Persistent segment tree

Query complexity: O(logN)
Update complexity: O(logN)
Additional memory: O(NlogN)

Test: http://www.spoj.com/problems/MKTHNUM/
*/

#include <bits/stdc++.h>
#define mid (left+right)/2
using namespace std;

const int N=1e5+10;
const int LogN=20;

struct Node
{
    int val;
    Node *l, *r;
};

vector<Node *> roots;
vector<pair<int, int> > v;
map<int, int> hmp;
int n, q, k;
int a[N];

void compress (vector<pair<int, int> > &v, int &k, int *a)
{
    sort (v.begin(), v.end());
    int last=-2e9;
    for (auto xt: v)
    {
        if (xt.first!=last) k++;
        a[xt.second]=k;
        hmp[k]=xt.first;
        last=xt.first;
    }
}

void init (Node *v, int left, int right)
{
    if (left==right) return;
    v->l=new Node();
    v->r=new Node();
    init (v->l, left, mid);
    init (v->r, mid+1, right);
}

void update (Node *v, Node *u, int left, int right, int x)
{
    v->val=u->val+1;
    if (left==right) return;

    if (x<=mid)
    {
        v->l=new Node();
        v->r=u->r;
        update (v->l, u->l, left, mid, x);
    }
    else
    {
        v->r=new Node();
        v->l=u->l;
        update (v->r, u->r, mid+1, right, x);
    }
}

int query (Node *v, int left, int right, int l, int r)
{
    if (l<=left && right<=r) return v->val;

    int ret=0;
    if (l<=mid) ret+=query(v->l, left, mid, l, r);
    if (r>mid) ret+=query(v->r, mid+1, right, l, r);
    return ret;
}

int main()
{
    scanf ("%d%d", &n, &q);
    for (int i=1;i<=n;i++)
    {
        scanf ("%d", &a[i]);
        v.push_back({a[i], i});
    }

    compress(v, k, a);

    roots.push_back(new Node());
    init (roots[0], 1, n);
    for (int i=1;i<=n;i++)
    {
        roots.push_back(new Node());
        update (roots.back(), roots[(int)roots.size()-2], 1, n, a[i]);
    }

    while (q--)
    {
        int l, r, m;
        scanf ("%d%d%d", &l, &r, &m);

        int low=1, up=k, half, ret;
        while (low<=up)
        {
            half=(low+up)/2;
            int lpart=query(roots[l-1], 1, n, 1, half);
            int rpart=query(roots[r], 1, n, 1, half);
            if (rpart-lpart<m) low=half+1;
            else
            {
                up=half-1;
                ret=half;
            }
        }

        printf ("%d\n", hmp[ret]);
    }

    return 0;
}