跟2104一个模子，就是数据范围变大了一丢丢

辣鸡代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <cmath>
using namespace std;
#define CLR(x,y) memset(x,y,sizeof(x))
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;

const int N=100010;

struct seg
{
    int lson,rson;
    int cnt;
};
seg T[N*20];
int tot,arr[N],root[N];
vector<int>pos;

void init()
{
    tot=0;
    CLR(root,0);
    pos.clear();
}
void build(int &cur,int l,int r)
{
    cur=++tot;
    T[cur].cnt=0;
    if(l==r)
        return ;
    int mid=MID(l,r);
    build(T[cur].lson,l,mid);
    build(T[cur].rson,mid+1,r);
}
void update(int &cur,int ori,int l,int r,int val)
{
    cur=++tot;
    T[cur]=T[ori];
    ++T[cur].cnt;
    if(l==r)
        return ;
    int mid=MID(l,r);
    if(val<=mid)
        update(T[cur].lson,T[ori].lson,l,mid,val);
    else
        update(T[cur].rson,T[ori].rson,mid+1,r,val);
}
int query(int S,int E,int l,int r,int k)
{
    if(l==r)
        return l;
    int mid=MID(l,r);
    int cnt=T[T[E].lson].cnt-T[T[S].lson].cnt;
    if(k<=cnt)
        return query(T[S].lson,T[E].lson,l,mid,k);
    else
        return query(T[S].rson,T[E].rson,mid+1,r,k-cnt);
}
int main(void)
{
    int n,m,i,L,R,K;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        for (i=1; i<=n; ++i)
        {
            scanf("%d",arr+i);
            pos.push_back(arr[i]);
        }
        sort(pos.begin(),pos.end());
        pos.erase(unique(pos.begin(),pos.end()),pos.end());

        int SZ=(int)pos.size();
        build(root[0],1,SZ);
        for (i=1; i<=n; ++i)
        {
            arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+1;
            update(root[i],root[i-1],1,SZ,arr[i]);
        }
        while (m--)
        {
            scanf("%d%d%d",&L,&R,&K);
            int indx=query(root[L-1],root[R],1,SZ,K)-1;
            printf("%d\n",pos[indx]);
        }
    }
    return 0;
}