[Spoj] MKTHNUM - K-th Number

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : MKTHNUM - K-th Number
Source            : Spoj
Category          : Data Structure
Algorithm         : Persistent Segment Tree, Array Implementation
Verdict           : Accepted 

#include <bits/stdc++.h>
 
using namespace std;
 
#define fil(a, b)             fill(begin(a), end(a), b)
 
inline int read()             { int a; scanf("%d", &a); return a; }
 
static const int MAXN = 1e5 + 5;       // total number in the array
static const int SIZE = 13600000 + 5;  // total node in Persistent Segment Tree
                                       // use around 8*N*logN
int NODES;         // NODES : pointer of total nodes in Persistent Segment Tree
int l[SIZE];       // l[p]  : left child of node p
int r[SIZE];       // r[p]  : right child of node p
int st[SIZE];      // st[p] : associative value of node p
int version[MAXN]; // version[i] : stores root of i'th segment tree
 
int arr[MAXN], temp[MAXN];
map <int, int> mapper;
int rmapper[MAXN];
 
void init()
{
    NODES = 0;
    fil(l, 0);
    fil(r, 0);
    fil(st, 0);
}
 
// Creating new Nodes
 
int newleaf(int val)
{
    NODES++;
    int p = NODES;
    l[p] = r[p] = 0; // null
    st[p] = val;
    return p;
}
 
int newparrent(int lef, int rig)
{
    NODES++;
    int p = NODES;
    l[p] = lef;
    r[p] = rig;
    st[p] = st[lef] + st[rig]; // immediately update value from children
    return p;
}
 
// Build (Persistent Segment Tree)
int build(int a, int b)
{
    if (a == b) return newleaf(0);
    int mid = (a+b)>>1;
    return newparrent(build(a, mid), build(mid+1, b));
}
// Usage:
// int root = build(1, n);
 
// Point Update (Create new tree)
// return an int, a pointer to the new root of the tree
int update(int p, int a, int b, int pos, int val)
{
    if (a == b) return newleaf(st[p] + val);
    int mid = (a+b)>>1;
    if (pos <= mid) return newparrent(update(l[p], a, mid, pos, val), r[p]);
    else return newparrent(l[p], update(r[p], mid+1, b, pos, val));
}
// Usage:
// int new_version_root = update(old_version_root, 1, n, pos, val)
// Both roots are valid, you can query from both of them!
 
// Find K'th smallest number in the the range [l....r]
int kth(int root_l, int root_r, int a, int b, int k)
{
    if (a == b) return a;
    int size_left_child = st[ l[root_r] ] - st[ l[root_l] ];
    int mid = (a+b) >> 1;
    if (k <= size_left_child) return kth(l[root_l], l[root_r], a, mid, k);
    else return kth(r[root_l], r[root_r], mid+1, b, k-size_left_child);
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int n = read();
    int q = read();
    for (int i = 1; i <= n; i++)
    {
        arr[i] = read();
        temp[i] = arr[i];
    }
    int id = 0;
    sort(temp+1, temp+n+1);
    for (int i = 1; i <= n; i++)
    {
        int x = temp[i];
        if (mapper.count(x) == 0)
        {
            id++;
            mapper[x] = id;
            rmapper[id] = x;
        }
    }
    for (int i = 1; i <= n; i++) arr[i] = mapper[ arr[i] ];
    init();
    int N = id;
    version[0] = build(1, N);
    for (int i = 1; i <= N; i++) version[i] = update(version[i-1], 1, N, arr[i], 1);
    while (q--)
    {
        int L = read();
        int R = read();
        int K = read();
        int ans = kth(version[L-1], version[R], 1, N, K);
        printf("%d\n", rmapper[ans]);
    }
}