可持久化线段树-主席树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n,q;
namespace ZXTree{
    int totID = 0;
    int L[maxn << 5],R[maxn << 5],sumv[maxn << 5];
    int build(int l,int r){
        int id = ++totID;
        int mid = l + r >> 1;
        if(l != r){
            L[id] = build(l,mid);
            R[id] = build(mid+1,r);
        }
        return id;
    }
    int update(int preID,int l,int r,int x,int v){
        int id = ++totID;
        int mid = l + r >> 1;
        L[id] = L[preID],R[id] = R[preID],sumv[id] = sumv[preID] + v;
        if(l != r){
            if(x <= mid) L[id] = update(L[id],l,mid,x,v);
            else R[id] = update(R[id],mid+1,r,x,v);
        }
        return id;
    }
    int query(int u,int v,int l,int r,int k){
        if(l == r) return l;
        int mid = l + r >> 1;
        int lcnt = sumv[L[v]] - sumv[L[u]];
        if(lcnt >= k) return query(L[u],L[v],l,mid,k);
        else return query(R[u],R[v],mid+1,r,k-lcnt);
    }
}
int a[maxn],b[maxn],c[maxn];
int T[maxn];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) {
        scanf("%d",a+i);
        b[i] = a[i];
    }
    sort(a+1,a+1+n);
    int m = unique(a+1,a+1+n) - a - 1;
    T[0] = ZXTree::build(1,m);
    for(int i=1;i<=n;i++) {
        c[i] = lower_bound(a+1,a+1+m,b[i]) - a;
        T[i] = ZXTree::update(T[i-1],1,m,c[i],1);
    }
    while(q--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",a[ZXTree::query(T[l-1],T[r],1,m,k)]);
    }
    return 0;
}