主席树—K-th Number

题目链接：[[kuangbin]主席树 [Cloned] - Virtual Judge (vjudge.net)](https://vjudge.net/contest/448446#problem/A)

主席树的定义与作用

主席树，也称可持久化线段树，那么什么是可持久化线段树呢，即为一颗记录了所有更新过程的线段树。能够处理出从第i次更新到第j次更新的线段树变化，具体作用一会见例题。

主席树的功能

记录所有过程的线段树，按正常思维是需要开O(NM)这么大的空间的，时间也为O（nm），n为线段树节点数，m为更新次数，但是使用主席树，就只需要开O

ACCode

#include<bitset>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn = 100005;

int n, q;
int Tree[20][maxn], a[maxn];

void Pushup(int l, int mid, int r, int deep) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (Tree[deep + 1][i] <= Tree[deep + 1][j])
            Tree[deep][k++] = Tree[deep + 1][i++];
        else
            Tree[deep][k++] = Tree[deep + 1][j++];
    }
    while (i <= mid) Tree[deep][k++] = Tree[deep + 1][i++];
    while (j <= r) Tree[deep][k++] = Tree[deep + 1][j++];
}

void Build(int l, int r, int deep) {
    if (l == r) {
        Tree[deep][l] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, deep + 1);
    Build(mid + 1, r, deep + 1);
    Pushup(l, mid, r, deep);
}


int Query(int L, int R, int l, int r, int k, int deep) {
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) return lower_bound(&Tree[deep][l], &Tree[deep][r] + 1, k) - &Tree[deep][l];  //用lower_bound时注意啦！！！！！！

    int mid = (l + r) >> 1;
    return  Query(L, R, l, mid, k, deep + 1) + Query(L, R, mid + 1, r, k, deep + 1);

}


int Solve(int L, int R, int k) {
    int l = 1, r = n + 1;          //二分。。。。。别写挂了
    for (int i = 1; i <= 30; i++) {
        int mid = (l + r) >> 1;
        int cnt = Query(L, R, 1, n, Tree[1][mid], 1);
        if (cnt <= k) l = mid;
        else r = mid;
    }
    return Tree[1][l];
}

int main()
{
    while (scanf("%d%d", &n, &q) != EOF) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        Build(1, n, 1);

        for (int i = 1; i <= q; i++) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", Solve(l, r, k - 1));
        }
    }
    return 0;
}