主席树 浅显学习

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int root[maxn * 40], lc[maxn * 40], rc[maxn * 40], sum[maxn * 40];
int tot = 0;

void build(int &id,int l,int r)
{
    id = ++tot;
    sum[id] = 0;
    int mid = (l + r) >> 1;
    if (l == r) return;
    build(lc[id], l, mid);
    build(rc[id], mid + 1, r);
}

int update(int id,int l,int r,int val)
{
    int rt = ++tot;
    sum[rt] = sum[id] + 1;
    lc[rt] = lc[id], rc[rt] = rc[id];
    if (l == r) return rt;
    int mid = (l + r) >> 1;
    if (val <= mid) lc[rt] = update(lc[rt], l, mid, val);//如果我们要放进去的这个数比这个mid要小，就往小的这边更新
    else rc[rt] = update(rc[rt], mid + 1, r, val);//反之就是往大的这边更新。
    return rt;
}

int query(int u,int v,int l,int r,int k)//u 是第一个区间，v是第二个区间
{
    int mid = (l + r) >> 1;
    int x = sum[lc[u]] - sum[lc[v]];//sum 相减 表示这个区间里面的数有多少
    if (l == r) return l;//如果l==r到达叶子节点 就说明找到了
    if (k <= x) return query(lc[u], lc[v], l, mid, k);//如果第k大要比左区间的数量小，则说明在左区间
    return query(rc[u], rc[v], mid + 1, r, k - x);//如果在右区间，那么应该要减去左区间的个数
}//这个sum其实存的是数量，我们求第k大其实就是找这一段区间的第k个数是什么，如果在右区间，那么应该是右区间的 第 k-sum[]大

int a[maxn], b[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    build(root[0], 1, len);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
        root[i] = update(root[i - 1], 1, len, a[i]);
    }
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        int ans = query(root[r], root[l - 1], 1, len, k);
        printf("%d\n", b[ans]);
    }
    return 0;
}