主席树

#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6;
int tot,n,m;
int sum[(maxn<<5)+10],rt[maxn+10],ls[(maxn<<5)+10],rs[(maxn<<5)+10];
int a[maxn+10],ind[maxn+10],len;
inline int getid(const int& val) {
    return lower_bound(ind+1,ind+len+1,val) - ind;
}

int build(int l,int r) {
    int root = ++tot;
    if(l == r) return root;
    int mid = l + r >> 1;
    ls[root] = build(l,mid);
    rs[root] = build(mid+1,r);
    return root;
}

int update(int k,int l,int r,int root) {
    int dir = ++tot;
    ls[dir] = ls[root],rs[dir] = rs[root], sum[dir] = sum[root] + 1;
    if(l == r) return dir;
    int mid = l + r >> 1;
    if(k <= mid) ls[dir] = update(k,l,mid,ls[dir]);
    else rs[dir] = update(k,mid+1,r,rs[dir]);
    return dir;
}

int query(int u,int v,int l,int r,int k) {
    int mid = l + r >>1;
    int x = sum[ ls[v] ] - sum[ ls[u] ];
    if(l == r) return l;
    if(k <= x) return query(ls[u],ls[v],l,mid,k);
    else return query(rs[u],rs[v],mid+1,r,k-x);
}

inline void init() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memcpy(ind,a,sizeof(ind));
    sort(ind+1,ind+1+n);
    len = unique(ind+1,ind+1+n) - ind - 1;
    rt[0] = build(1,len);
    for(int i=1;i<=n;i++) rt[i] = update(getid(a[i]),1,len,rt[i-1]);
}

int l,r,k;
inline void solve() {
    while(m--) {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",ind[query(rt[l-1],rt[r],1,len,k)]);
    }
}


int main() {
    init();
    solve();
    return 0;
}