平方分割一直TLE，最后用归并树处理过了，使用STL会比较慢。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1 const int N = 100008, INF = 0x3F3F3F3F;
int tp[N], a[N];
vector<int> v[N << 2]; void build(int l, int r, int rt){
if(l == r){
v[rt].clear();
v[rt].push_back(a[l]);
}else{
int mid = (l + r) >> 1;
build(lson);
build(rson);
v[rt].resize(r - l + 1);
merge(v[rt << 1].begin(), v[rt << 1].end(), v[rt << 1 | 1].begin(), v[rt << 1 | 1].end(), v[rt].begin());
}
} int query(int a, int b, int l, int r, int rt, int x){
if(a <= l && b >= r){
return upper_bound(v[rt].begin(), v[rt].end(), x) - v[rt].begin();
} int mid = (l + r) >> 1;
int cnt = 0;
if(a <= mid){
cnt += query(a, b, lson, x);
}
if(b > mid){
cnt += query(a, b, rson, x);
}
return cnt;
} int main(){
int n, q;
while(~scanf("%d %d", &n, &q)){
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
tp[i] = a[i];
}
build(0, n - 1, 1);
sort(tp, tp + n);
int cnt = unique(tp, tp + n) - tp;
while(q--){
int a, b, k;
scanf("%d %d %d", &a, &b, &k);
a--;
b--;
int l = 0, r = cnt;
while(l < r){
int mid = (l + r ) >> 1;
if(query(a, b, 0, n - 1, 1, tp[mid]) < k){
l = mid + 1;
}else{
r = mid;
}
}
printf("%d\n", tp[l]);
} } return 0;
}