[Spoj] MKTHNUM - K-th Number

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : MKTHNUM - K-th Number
Source            : Spoj
Category          : Data Structure, Search
Algorithm         : Persistent Segment Tree, Binary Search
Verdict           : Accepted 
Find k'th in the interval [l, r] using Binary Search.

#include <bits/stdc++.h>
 
using namespace std;
 
static const int MAXN = 1e5 + 5;
 
map <int, int> arrTOind, indTOarr;
 
int n, q;
int arr[MAXN], temp[MAXN];
 
struct node
{
    int val;
    node *left, *right;
    node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
} *version[MAXN<<2];
 
void build(node *root, int a, int b)
{
    if (a > b) return;
    if (a == b)
    {
        root->val = 0;
        return;
    }
    int mid = (a+b) >> 1;
    root->left = new node(0);
    root->right = new node(0);
    build(root->left, a, mid);
    build(root->right, mid+1, b);
    root->val = root->left->val + root->right->val;
}
 
void update(node *proot, node *root, int a, int b, int pos)
{
    if (a > b || a > pos || b < pos) return;
    if (a >= pos && b <= pos)
    {
        root->val += 1;
        return;
    }
    int mid = (a+b) >> 1;
    if (pos <= mid)
    {
        root->left = new node(0);
        root->right = proot->right;
        update(proot->left, root->left, a, mid, pos);
    }
    else
    {
        root->right = new node(0);
        root->left = proot->left;
        update(proot->right, root->right, mid+1, b, pos);
    }
    root->val = root->left->val + root->right->val;
}
 
int query(node *root, int a, int b, int i, int j)
{
    if (a > b || a > j || b < i) return 0;
    if (a >= i && b <= j) return root->val;
    int mid = (a+b) >> 1;
    int p1 = query(root->left, a, mid, i, j);
    int p2 = query(root->right, mid+1, b, i, j);
    return p1+p2;
}
 
int queryAns(int l, int r, int k)  // count total number less than 
{                                  // equal to k in [l, r]
    int sumr = query(version[r], 1, n, 1, k);
    int suml = query(version[l-1], 1, n, 1, k);
    return sumr - suml;
}
 
int binarySearch(int l, int r, int k)
{
    int low = 1;
    int high = n;
    int ans;
    while (low <= high)
    {
        int mid = (low+high) >> 1;
        int cnt = queryAns(l, r, mid);
        if (cnt >= k)
        {
            ans = mid;
            high = mid-1;
        }
        else
        {
            low = mid+1;
        }
    }
    return ans;
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
        temp[i] = arr[i];
    }
    sort(temp+1, temp+n+1);
    int id = 0;
    for (int i = 1; i <= n; i++)
    {
        int num = temp[i];
        if (arrTOind.count(num) == 0)
        {
            id++;
            arrTOind[num] = id;
            indTOarr[id] = num;
        }
    }
    for (int i = 1; i <= n; i++) arr[i] = arrTOind[arr[i]];
    version[0] = new node(0);
    build(version[0], 1, n);
    for (int i = 1; i <= n; i++)
    {
        int pos = arr[i];
        version[i] = new node(0);
        update(version[i-1], version[i], 1, n, pos);
    }
    while (q--)
    {
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k);
        int ans = binarySearch(l, r, k);
        printf("%d\n", indTOarr[ans]);
    }
}