静态区间第k大的问题，往往可以利用主席树来解决
这是主席树的第一道题
主席树大概可以理解为在n个节点上都建立一棵线段树，但是想想会超出内存
每一个节点保存的线段树都记录当前整段前缀区间的信息
但是因为每次添加后一个节点，那么他除了当前节点位置需要更新之外，其他的位置都可以保持跟上一棵节点对应的线段树一致，那么为了缩小内存，
将那些不需要改变的点的指针指向上一棵树对应的节点即可，其他多生成的节点也就是需要更新的节点，最多不超过log2n个，所以最后产生的线段树的
点的个数大概在nlogn的大致范围内
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 100005
#define M int m=(l+r)>>1
#define LS(o) node[o].ls
#define RS(o) node[o].rs int n , m , a[N] , b[N] , T[N]; struct Node{
int sz , ls , rs;
void init(){sz=;ls=rs=;}
}node[N*]; int tot; int build(int l , int r)
{
int u = tot++;
node[u].init();
if(l!=r){
M;
node[u].ls = build(l , m);
node[u].rs = build(m+ , r);
}
return u;
} void build(int o1 , int o2 , int l , int r , int pos)
{
node[o2].init();
node[o2].sz = node[o1].sz+;
M;
if(l == r) return;
if(pos<=m){
node[o2].ls = tot++ , node[o2].rs = RS(o1);
build(LS(o1) , LS(o2) , l , m , pos);
}
else {
node[o2].rs = tot++ , node[o2].ls = LS(o1);
build(RS(o1) , RS(o2) , m+ , r , pos);
}
} int query(int o1 , int o2 , int l , int r , int k)
{
if(l==r) return l;
M;
int tmp;
if((tmp=node[LS(o2)].sz - node[LS(o1)].sz)>=k) return query(LS(o1) , LS(o2) , l , m , k);
else return query(RS(o1) , RS(o2) , m+ , r , k-tmp);
} int main()
{
// freopen("in.txt" , "r" , stdin);
while(~scanf("%d%d" , &n , &m)){
for(int i= ; i<=n ; i++)scanf("%d" , a+i);
for(int i= ; i<=n ; i++)b[i]=a[i];
sort(b+ , b+n+);
tot = ;
T[] = build( , n);
for(int i= ; i<=n ; i++){
int pos = lower_bound(b+ , b+n+ , a[i])-b;
T[i] = tot++;
build(T[i-] , T[i] , , n , pos);
}
while(m--){
int s , t , k;
scanf("%d%d%d" , &s , &t , &k);
int pos = query(T[s-] , T[t] , , n , k);
printf("%d\n" , b[pos]);
}
}
return ;
}