本题std
c++ 划分树版本

#include<cstdio>
#include<algorithm>
#define MID (l+r)>>1
const int MAXN=100000+5;
const int MAXL=20+1;
int tree[MAXL][MAXN],toleft[MAXL][MAXN],sorted[MAXN];
void BuildTree(int layer,int l,int r)
{
    if(l==r) return;
    int mid=MID;
    int cnt=mid-l+1;
    for(int i=l;i<=r;i++)
        if(tree[layer][i]<sorted[mid]) cnt--;
    int lpos=l,rpos=mid+1;
    for(int i=l;i<=r;i++)
    {
        if(i==l) toleft[layer][i]=0; else toleft[layer][i]=toleft[layer][i-1];
        if(tree[layer][i]<sorted[mid])
        {
            toleft[layer][i]++;
            tree[layer+1][lpos++]=tree[layer][i];
        }
        else if(tree[layer][i]>sorted[mid])
        {
            tree[layer+1][rpos++]=tree[layer][i];
        }
        else
        {
            if(cnt)
            {
                cnt--;
                toleft[layer][i]++;
                tree[layer+1][lpos++]=tree[layer][i];
            }
            else tree[layer+1][rpos++]=tree[layer][i];
        }
    }
    BuildTree(layer+1,l,mid);
    BuildTree(layer+1,mid+1,r);
}
int Query(int layer,int l,int r,int ql,int qr,int k)
{
    if(ql==qr) return tree[layer][ql];
    int mid=MID;
    int s,ss;
    if(ql==l)
    {
        s=0;
        ss=toleft[layer][qr];
    }
    else
    {
        s=toleft[layer][ql-1];
        ss=toleft[layer][qr]-s;
    }
    int newl,newr;
    if(k<=ss)
    {
        newl=l+s;
        newr=l+s+ss-1;
        return Query(layer+1,l,mid,newl,newr,k);
    }
    else
    {
        newl=mid-l-s+ql+1;
        newr=mid-l-s-ss+qr+1;
        return Query(layer+1,mid+1,r,newl,newr,k-ss);
    }
}
int main()
{
    int n,m,x,y,z;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&tree[0][i]);
        sorted[i]=tree[0][i];
    }
    std::sort(sorted+1,sorted+n+1);
    BuildTree(0,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        printf("%d\n",Query(0,1,n,x,y,z));
    }
}

另外还可以用可持久化线段树/主席树

暴力分为31分