可持久化权值线段树（主席树）

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
const LL N = 200005;
struct tree {//L为左儿子， R为右儿子，sum为该节点的权值
    int L;
    int R;
    LL sum;
}t[N << 5];//每个数离散化为1 - n后，储存在对应的下标
int cnt, tot, n, m, a[N], b[N], c[N], root[N];

int build(int l, int r)//初始化空树， 实际上没必要
{
    int rt = ++cnt;
    if(l == r) return rt;
    int mid = l + r >> 1;
    t[rt].L = build(l, mid);
    t[rt].R = build(mid + 1, r);
    return rt;
}

int change(int pre, int l, int r, int x)//建一棵只有logN个节点的线段树
{
    int rt = ++cnt;//新建节点，下面动态开点
    t[rt].L = t[pre].L;//继承前一棵树的左右子节点， 再做修改
    t[rt].R = t[pre].R;
    t[rt].sum = t[pre].sum + 1;//前一棵树相同位置上加一
    if(l == r) return rt;

    int mid = l + r >> 1;
    if(x <= mid) 
        t[rt].L = change(t[pre].L, l, mid, x);//x在左子树，修改左子树
    else 
        t[rt].R = change(t[pre].R, mid + 1, r, x);//x在右子树同理

    return rt; //返回当前分配使用新节点的编号
}

int query(int x, int y, int l, int r, int k)
{
    if(l >= r) return l; 
    int dta = t[t[y].L].sum - t[t[x].L].sum;//线段树相减，看左节点个数
    int mid = l + r >> 1;
    if(dta >= k) //左儿子大于等于k时，在左儿子第k个
        return query(t[x].L, t[y].L, l, mid, k);
    else //否则在右儿子第k - dta个
        return query(t[x].R, t[y].R, mid + 1, r, k - dta);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++)
    {
        if(b[i] != b[i - 1] || i == 1)//离散化去重
        c[++tot] = b[i];
    }
    // root[0] = build(1, tot);
    for(int i = 1; i <= n; i++)
    {
        int u = lower_bound(c + 1, c + tot + 1, a[i]) - c;
        root[i] = change(root[i - 1], 1, tot, u);//建第i棵线段树，root[i]是对应的根节点
    }

    int u, v, w;
    for(int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        int t = query(root[u - 1], root[v], 1, tot, w);//第y棵线段树-第x-1棵线段树，是[x, y]的线段树
        cout << c[t] << '\n';
    }
    return 0;

}