静态主席树

#include<bits/stdc++.h>
#define int long long
#define maxn 50000
using namespace std;
inline char get(){
    static char buf[30000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f; 
}
int num,n,q;
int a[maxn],b[maxn],c[maxn],T[maxn];
int lc[maxn<<5],rc[maxn<<5],tree[maxn<<5];
int build(int l,int r){
    int id=++num,mid=(l+r)>>1;
    if(l!=r){
        lc[id]=build(l,mid);
        rc[id]=build(mid+1,r);
    }
    return id;
}
int update(int pre_id,int l,int r,int x,int v){
    int id=++num,mid=(l+r)>>1;
    lc[id]=lc[pre_id],rc[id]=rc[pre_id],tree[id]=tree[pre_id]+v;
    if(l!=r){
        if(x<=mid)lc[id]=update(lc[id],l,mid,x,v);
        else rc[id]=update(rc[id],mid+1,r,x,v);
    }
    return id;
}
int query(int l,int r,int x,int y,int k){
    if(l==r)return l;
    int mid=(l+r)>>1;
    int cas_l=tree[lc[y]]-tree[lc[x]];
    if(cas_l>=k)return query(l,mid,lc[x],lc[y],k);
    else return query(mid+1,r,rc[x],rc[y],k-cas_l);
}
signed main(){
    n=read(),q=read();
    for(register int i=1;i<=n;i++)a[i]=b[i]=read();
    sort(a+1,a+1+n);
    int m=unique(a+1,a+1+n)-a-1;
    T[0]=build(1,m);
    for(register int i=1;i<=n;i++)c[i]=lower_bound(a+1,a+1+m,b[i])-a,T[i]=update(T[i-1],1,m,c[i],1);
    while(q--){
        int l=read(),r=read(),k=read();
        cout<<a[query(1,m,T[l-1],T[r],k)]<<endl;
    }
    return 0;
}