[cpp]
//為了做一道題，以前不知道什麼劃分樹，只能從最基本的學，這是入門題，看了別人了代碼，然後慢慢寫的
[cpp]
#include <iostream>
using namespace std ;
const int MAXN = 100010 ;
int data[30][MAXN], sorted[MAXN], toleft[30][MAXN] ;
int cmp(const void *a, const void *b){
return *(int *)a < *(int *)b ? -1 : 1 ;
}
void build(int l, int r, int d){
if(l==r) return ;
int i ;
int m = (l + r) >> 1 ;
int ls = m - l + 1 ; //用來標記和中間值m相等的，且分到左孩子的數的個數。
//初始時，假定當前區間[l,r]有mid-l+1個和m 相等。
//先踢掉比中間值小的,剩下的就是要插入到左邊的*/
for(i=l; i<=r; i++)
if(data[d][i]<sorted[m])
ls -- ; //踢掉比中間值小的
int lp = l ;
int rp = m + 1 ;
for(i=l; i<=r; i++){
if(i==l)
toleft[d][i] = 0 ; //// 初始一個子樹。
else
toleft[d][i] = toleft[d][i-1] ; //// 初始區間下一個節點。
/* 如果大於，肯定進入右孩子，否則，判斷是否還有相等的應該進入左孩子的，
沒有，就直接進入右孩子，否則進入左孩子*/
if(data[d][i]<sorted[m]){
toleft[d][i]++;
data[d+1][lp++] = data[d][i] ;
}else if(data[d][i]>sorted[m])
data[d+1][rp++] = data[d][i] ;
else{ //考慮相等
if(ls){ // 相等分到做孩子的數目>0
ls -- ;
toleft[d][i]++ ;
data[d+1][lp++] = data[d][i] ;
}else data[d+1][rp++] = data[d][i] ;
}
}
build(l, m, d+1) ;
build(m+1, r, d+1) ;
}
int query(int L, int R, int k, int l, int r, int d){ //在[L,R]區間尋找小於第k 的元素，總區間[l,r]
if(L==R) return data[d][L] ;
int m = (l + r) >> 1 ;
int lLR, llL, rLR, rlL ;
if(L==l){
lLR = toleft[d][R] ; //lLR 左邊小於第k個元素的數量
llL = 0 ; //llL 記錄區間[lft, a-1)中計入左孩子的元素的個數。
}else{
lLR = toleft[d][R] - toleft[d][L-1] ; //
llL = toleft[d][L-1] ;
}
int nl, nr ;
if(lLR>=k){
nl = l + llL ; //記錄區間[L, R]中進入左孩子的元素的個數。
nr = l + lLR + llL - 1 ; //
return query(nl, nr, k, l, m, d+1) ;
}else{
rlL = L - l - llL ; //表示[L, R] 中分到右孩子的個數
rLR = R - L + 1 - lLR ; //表示[lft, a-1]中分到右孩子的個數
nl = m + 1 + rlL ;
nr = m + rlL + rLR ;
return query(nl, nr, k-lLR, m+1, r, d+1) ;
}
}
int main(){
int n, m, i, j, l, r, k ;
while(~scanf("%d%d",&n,&m)){
for(i=1; i<=n; i++){
scanf("%d",&data[0][i] );
sorted[i] = data[0][i] ;
}
qsort(sorted+1, n, sizeof(int), cmp) ;
build(1, n, 0);
while(m--){
scanf("%d%d%d", &l, &r, &k) ;
printf("%d\n",query(l, r, k, 1, n, 0)) ;
}
}
return 0 ;
}
