boj7469.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
  
using namespace std;
  
#define MAXN 100100
  
vector<vector<int> > tree;
vector<int> varr;
int arr[MAXN], N, M, a, b, c, p=1;
  
void init_tree(){
    while(N > p ) p <<=1;
    tree.resize(4*N);
      
    for(int i = 0; i < N ; i++)
        tree[i+p].push_back(arr[i]);
      
    for(int i = p-1 ; i>= 1; i--){
        for(int j = 0  ; j < tree[i*2].size() ; j++)
            tree[i].push_back(tree[i*2][j]);
        for(int j= 0 ;  j < tree[i*2+1].size() ; j++)
            tree[i].push_back(tree[i*2+1][j]);
        sort(tree[i].begin(), tree[i].end());
    }
}
  
int find_pre(int l, int r, int v){
    l += p, r += p;
    int pre=0;
    while(l <= r){
        if(l&1){
            pre += (lower_bound(tree[l].begin(), tree[l].end(), v)- tree[l].begin());
            l++;
        }
        if(!(r&1)){
            pre += (lower_bound(tree[r].begin(), tree[r].end(), v)-tree[r].begin());
            r--;
        }
        l >>=1, r >>=1;
    }
    return pre;
}
  
int main(){
    cin >> N >> M;
    for(int i = 0 ; i< N ; i++){
        scanf("%d", &arr[i]);
        varr.push_back(arr[i]);
    }
    sort(varr.begin(), varr.end());
    for(int i = 0 ; i < N; i++)
        arr[i] = (int)(lower_bound(varr.begin(), varr.end(), arr[i])-varr.begin());
  
    init_tree();
  
    for(int j=1 ; j<= M ; j++){
        scanf("%d%d%d", &a, &b, &c);
        int l=0, r= N, m;
        while(l != r){
            m = (l+r+1)/2;
            if(find_pre(a-1, b-1, m) +1 <= c)
                l = m;
            else
                r = m-1;
        }
        cout << varr[l] << endl;
    }
    return 0;
}