主席树

注意事项：

1. 记主席树开在长度为 $n$ 的区间上，操作数为 $m$，$\text{lay}n=\lceil\log n\rceil+1$，标记永久化版的最大空间占用量（若初始版本为空）为 $m\text{lay}n$。

2. 函数 modify 等有两种写法，「传入 id」和「不传入 id，返回 id」，建议使用后一种。

Luogu P3834 【模板】可持久化线段树 2

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 2e5;
const int MAXa = 1e9;
const int MAXlay = 32;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

const int MAXnd = MAXn * MAXlay;
int root[MAXn + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10];
int siz[MAXnd + 10];
inline void pushup(int id) {
    siz[id] = siz[ls[id]] + siz[rs[id]];
}
inline void clone(int id, int verid) {
    ls[id] = ls[verid];
    rs[id] = rs[verid];
    siz[id] = siz[verid];
}
int modify(int verid, int p, int le, int ri) {
    int id = ++cntnd;
    clone(id, verid);
    if (le == ri) {
        ++siz[id];
    } else {
        int mid = (le + ri) >> 1;
        if (p <= mid) ls[id] = modify(ls[verid], p, le, mid);
        else rs[id] = modify(rs[verid], p, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int query(int lid, int rid, int rk, int le, int ri) {
    if (le == ri) {
        return le;
    } else {
        int mid = (le + ri) >> 1;
        int tmp = siz[ls[rid]] - siz[ls[lid]];
        if (rk <= tmp) {
            return query(ls[lid], ls[rid], rk, le, mid);
        } else {
            return query(rs[lid], rs[rid], rk - tmp, mid + 1, ri);
        }
    }
}

int n, m;

signed main() {
    read(n, m);
    for (int i = 1, a; i <= n; ++i) {
        read(a);
        root[i] = modify(root[i - 1], a, -MAXa, MAXa);
    }
    for (int i = 1, l, r, rk; i <= m; ++i) {
        read(l, r, rk);
        printf("%d\n", query(root[l - 1], root[r], rk, -MAXa, MAXa));
    }
    return 0;
}