主席树（模板）

感谢&资料：

感谢 bLue 学长的讲堂（虽然之前就差不多学会了），和卿学姐的视频。

简介：

只是刚入门，这里当做存一个模板，主席树的功能是可以存储历史版本的线段树，然后可以干很多神奇的事情。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 112345;

struct Node {
    int sum, l, r;
} tree[MAX * 40];

int root[MAX], cnt;
int data[MAX];
vector<int> sorted;

//离散化获得ID
int get_id(int x) {
    return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
}

void init() {
    cnt = 0;
    root[0] = 0;
}

//根据旧版本的线段树创建新线段树的节点
int create_node(int po) {
    int idx = ++cnt;
    tree[idx].sum = tree[po].sum + 1;
    tree[idx].l = tree[po].l;
    tree[idx].r = tree[po].r;
    return idx;
}

void updata(int &o, int po, int l, int r, int pos) {
    o = create_node(po);
    if (l == r) return;
    int m = (l + r) >> 1;
    if (pos <= m) updata(tree[o].l, tree[po].l, l, m, pos);
    else updata(tree[o].r, tree[po].r, m + 1, r, pos);
}

//二分查询
int query(int s, int e, int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) >> 1;
    int sum = tree[tree[e].l].sum - tree[tree[s].l].sum;
    if (k <= sum) return query(tree[s].l, tree[e].l, l, m, k);
    else return query(tree[s].r, tree[e].r, m + 1, r, k - sum);
}

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &data[i]);
            sorted.push_back(data[i]);
        }
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        int num = sorted.size();
        for (int i = 1; i <= n; i++) {
            updata(root[i], root[i - 1], 1, num, get_id(data[i]));
        }
        for (int i = 1; i <= m; i++) {
            int x, y, k;
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", sorted[query(root[x - 1], root[y], 1, num, k) - 1]);
        }
    }
}