主席树(可持续化线段树),静态,求区间的第K小数,离散化后在原数列值域上建立线段树,表视在某个区间内出现的数的数量,依次添加a[i],root[i]储存当前状态的根节点序号,递归查找
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    int lc,rc,num;
}t[N*20];
vector<int> alls;
int find(int x) 
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; 
}
int tot,root[N];
int a[N];
int build(int l,int r)
{
    int p=++tot;
    if(l==r)
    {
        t[p].num=0;
        return p;
    }
    int mid=(l+r)>>1;
    t[p].lc=build(l,mid);
    t[p].rc=build(mid+1,r);
    t[p].num=t[t[p].lc].num+t[t[p].rc].num;
    return p;
}
int insert(int now,int l,int r,int x,int val)
{
    int p=++tot;
    t[p]=t[now];
    if(l==r)
    {
        t[p].num+=val;
        return p;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        t[p].lc=insert(t[now].lc,l,mid,x,val);
    }else
    {
        t[p].rc=insert(t[now].rc,mid+1,r,x,val);
    }
    t[p].num=t[t[p].lc].num+t[t[p].rc].num;
    return p;
}
int query(int p,int q,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    int mid=(l+r)>>1;
    int lnum=t[t[p].lc].num-t[t[q].lc].num;
    if(k<=lnum)
    {
        return query(t[p].lc,t[q].lc,l,mid,k);
    }else
    {
        return query(t[p].rc,t[q].rc,mid+1,r,k-lnum);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        alls.push_back(a[i]);
    }
    sort(alls.begin(), alls.end()); 
    alls.erase(unique(alls.begin(), alls.end()), alls.end());   
    root[0]=build(1,alls.size());
    for(int i=1;i<=n;i++)
    {
        root[i]=insert(root[i-1],1,alls.size(),find(a[i]),1);
    }
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<alls[query(root[r],root[l-1],1,alls.size(),k)-1]<<endl;
    }
    return 0;
}