样例不过求调

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
const int N=2e5+10;
struct node{int l,r,v;};
int n,m,q,cnt,a[N],b[N],rt[N];
node tr[N<<5];
inline int build(int pre,int l,int r,int x) {
    int p=++cnt;
    tr[p]={tr[pre].l,tr[pre].r,tr[pre].v+1};
    if(l<r) {
        if(x<=mid) tr[p].l=build(tr[pre].l,l,mid,x);
        else tr[p].r=build(tr[pre].r,mid+1,r,x);
    }
    return p;
}
inline int query(int L,int R,int l,int r,int k) {
    if(l==r) return l;
    int x=tr[tr[L].l].v-tr[tr[R].l].v;
    if(x>=k) return query(tr[L].l,tr[R].l,l,mid,k);
    else return query(tr[L].r,tr[R].r,mid+1,r,k-x);
}
signed main() {
    ios::sync_with_stdio(NULL);
    cin>>n>>q,m=n;
    for(int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+m),m=unique(b+1,b+1+m)-b-1;
    for(int i=1;i<=n;++i) {
        int x=lower_bound(b+1,b+1+m,a[i])-b;
        rt[i]=build(rt[i-1],1,m,x);
    }
    while(m--) {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[query(rt[l-1],rt[r],1,m,k)]<<endl;
    }
    return 0;
}