主席树

#include <iostream>
#include <cstdio>
#include <algorithm>
#define mid ((l+r)>>1)

using namespace std;

const int maxn=2e5+10;

int cnt=0,sum[maxn<<5],lc[maxn<<5],rc[maxn<<5];
int a[maxn],b[maxn],t[maxn];

inline int build(int l,int r)
{
    int rt=++cnt;
    sum[rt]=0;
    if(l<r)
    {
        lc[rt]=build(l,mid);
        rc[rt]=build(mid+1,r);
    }
    return rt;
}

inline int update(int pre,int l,int r,int x)
{
    int rt=++cnt;
    lc[rt]=lc[pre];rc[rt]=rc[pre];sum[rt]=sum[pre]+1;
    if(l<r)
    {
        if(x<=mid)
            lc[rt]=update(lc[pre],l,mid,x);
        else
            rc[rt]=update(rc[pre],mid+1,r,x);
    }
    return rt;
}

inline int query(int x,int y,int l,int r,int k)
{
    if(l>=r)
        return l;
    int q=sum[lc[y]]-sum[lc[x]];
    if(q>=k)
        return query(lc[x],lc[y],l,mid,k);
    else
        return query(rc[x],rc[y],mid+1,r,k-q);
}

int main()
{

    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    t[0]=build(1,len);
    for(int i=1;i<=n;i++)
    {
        int tmp=lower_bound(b+1,b+len+1,a[i])-b;
        t[i]=update(t[i-1],1,len,tmp);
    }
    int x,y,z;
    while(m--)
    {
        scanf("%d %d %d",&x,&y,&z);
        printf("%d
",b[query(t[x-1],t[y],1,len,z)]);
    }
    return 0;
}