[UVa] 13183 - Tobby and Array

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13183 - Tobby and Array
Source            : UVa Online Judge
Category          : Data Structure
Algorithm         : Persistent Segment Tree
Verdict           : Accepted


Works for duplicate values........ 

#include <bits/stdc++.h>
 
using namespace std;
 
#define fil(a, b)              fill(begin(a), end(a), b)
 
static const int MAXN = 1e6 + 6;
static const int SIZE = 8e7 + 7;
 
int arr[MAXN], rmapper[MAXN];
 
int NODES, l[SIZE], r[SIZE], st[SIZE];
int version[MAXN];
 
void init()
{
    NODES = 0;
    fil(l, 0);
    fil(r, 0);
    fil(st, 0);
}
 
int newleaf(int val)
{
    NODES++;
    int p = NODES;
    l[p] = r[p] = 0; 
    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];
    return p;
}
 
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));
}
 
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));
}
 
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);
}
 
struct Node
{
    int val, ind;
    Node() {}
    Node(int val, int ind)
    {
        this->val = val;
        this->ind = ind;
    }
    friend bool operator < (Node A, Node B)
    {
        if (A.val == B.val) return A.ind < B.ind;
        return A.val < B.val;
    }
} temp[MAXN];
 
int main()
{
    int n, q;
 
    while (scanf("%d %d", &n, &q) == 2)
    {
        //init();
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", arr+i);
            temp[i].ind = i;
            temp[i].val = arr[i];
        }
        sort(temp+1, temp+n+1);
        int id = 0;
 
        for (int i = 1; i <= n; i++)
        {
            int ind = temp[i].ind;
            int val = temp[i].val;
 
            id++;
 
            arr[ind] = id;
            rmapper[id] = val;
        }
        int N = id;
        NODES = 0;
        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, r, k;
            scanf("%d %d %d", &l, &r, &k);
 
            if (l > r) swap(l, r);
 
            int pl = version[l-1]; // segment tree of index 'l-1'
            int pr = version[r];
 
            int ans = kth(pl, pr, 1, N, k);
 
            printf("%d\n", rmapper[ans]);
        }
    }
}