主席树（可持久化线段树） 静态第k大

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
/*
可持久化线段树，函数式线段树，主席树
动态第k大

线段树维护的是值出现的次数
*/
const int N = 100010;
int a[N], t[N];
int T[N * 30], lson[N * 30], rson[N * 30], c[N * 30];
int total, n, q, m;
void initHash()
{
    for (int i = 1; i <= n; ++i)
        t[i] = a[i];
    sort(t + 1, t + n + 1);
    m = unique(t + 1, t + n + 1) - t - 1;

}

int Hash(int x)
{
    return lower_bound(t + 1, t + m + 1, x) - t;
}
int build(int l, int r)//建一棵区间长度为m的线段树，  每个节点的值都是0
{
    int root = total++;
    c[root] = 0;
    if (l != r)
    {
        int mid = (l + r) >> 1;
        lson[root] = build(l, mid);
        rson[root] = build(mid + 1, r);
    }
    return root;
}
// T[i] 和T[i+1]相比， 只更新了一条链，  所以可以借用T[i+1]的一些子树来节省空间
// 按下标建树？
int update(int root, int pos, int val)
{
    int newRoot = total++, tmp = newRoot;
    c[newRoot] = c[root] + val;
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (pos <= mid)//如果进入左子树， 那么右子树可以指向旧版本
        {
            lson[newRoot] = total++;
            rson[newRoot] = rson[root];
            newRoot = lson[newRoot];
            root = lson[root];
            r = mid;
        }
        else//左子树指向旧版本
        {
            rson[newRoot] = total++;
            lson[newRoot] = lson[root];
            newRoot = rson[newRoot];
            root = rson[root];
            l = mid + 1;
        }
        c[newRoot] = c[root] + val;
    }
    return tmp;
}
//每次插入都记录，它是插入左区间呢，还是右区间，  那么询问区间第k大时，只要该区间进入左区间的数字大于等于k，那么就去左子树找，
//否则， 缩小k，  去右区间找
int query(int leftRoot, int rightRoot, int k)
{
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        //c[lson[leftRoot]] - c[lson[rightRoot]] 表示区间内的数进入到左区间的有多少个
        if (c[lson[leftRoot]] - c[lson[rightRoot]] >= k)
        {
            r = mid;
            leftRoot = lson[leftRoot];
            rightRoot = lson[rightRoot];
        }
        else
        {
            l = mid + 1;
            k -= c[lson[leftRoot]] - c[lson[rightRoot]];
            leftRoot = rson[leftRoot];
            rightRoot = rson[rightRoot];
        }
    }
    return l;
}
int main()
{
    int  L, R, k;
    while (scanf("%d%d", &n, &q) == 2)
    {
        total = 0;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        initHash();
        T[n + 1] = build(1, m);
        for (int i = n; i; i--)
        {
            int pos = Hash(a[i]);
            T[i] = update(T[i + 1], pos, 1);
        }
        while (q--)
        {
            scanf("%d%d%d", &L, &R, &k);
            printf("%d\n", t[query(T[L], T[R + 1], k)]);
        }
    }
    return 0;
}