此代码同hdu2665改编
#include <iostream>

#include <cstdio>

#include<cstring>

#include <algorithm>

using namespace std;

#define N 100500

#define MID ((l+r)>>1)

int a[N],s[N],t[][N],num[][N],n,m;

void Build(int c,int l,int r)

{

    int lm=MID-l+,lp=l,rp=MID+;

    for(int i=l;i<=MID;i++)

        lm-=s[i]<s[MID];

    for(int i=l;i<=r;i++)

    {

        if( i==l )

            num[c][i]=;

        else

            num[c][i]=num[c][i-];

        if( t[c][i]==s[MID] )

        {

            if( lm )

            {

                lm--;

                num[c][i]++;

                t[c+][lp++]=t[c][i];

            }

            else

                t[c+][rp++]=t[c][i];

        }

        else if( t[c][i]<s[MID] )

        {

            num[c][i]++;

            t[c+][lp++]=t[c][i];

        }

        else

            t[c+][rp++]=t[c][i];

    }

    if( l<r )

        Build(c+,l,MID),Build(c+,MID+,r);

}

int Query(int c,int l,int r,int ql,int qr,int k)

{

    if( l==r )

        return t[c][l];

    int s,ss;

    if( l==ql )

        s=,ss=num[c][qr];

    else

        s=num[c][ql-],ss=num[c][qr]-num[c][ql-];

    if( k<=ss )

        return Query(c+,l,MID,l+s,l+s+ss-,k);

    else

        return Query(c+,MID+,r,MID++ql-l-s,MID++qr-l-s-ss,k-ss);

}

int main()

{

    scanf("%d%d",&n,&m);

    memset(t,,sizeof(t));

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        s[i]=t[][i]=a[i];

    }

    sort(s+,s++n);

    Build(,,n);

    while( m-- )

    {

        int l,r,k;

        scanf("%d%d%d",&l,&r,&k);

        printf("%d\n",Query(,,n,l,r,k));

    }

    return ;

}