没啥好说的概念，直接看题目。
MKTHNUM - K-th Number
考虑如果我们对每个操作进行二分怎么做。
显然是对这个区间不大于二分值 \(mid\) 的数统计个数，看个数 \(num\) 和 \(k\) 的大小关系。如果 \(num\) 更大，证明 \(mid\) 大了，如果 \(num\) 更小，证明 \(mid\) 小了。
然后我们考虑推广这种思路。
首先我们询问的答案肯定是原来数组中的一个数，所以我们可以直接把原数组排序，然后用下标代表其权值。这里我们的排序事实上可以用离散化完成，那样做的效果相同，但是排序更方便。
接下来，我们要实现整体二分的核心函数 \(solve(l,r,L,R)\)，表示当前对于编号为 \(id，id\in[l,r]\) 的询问，可能的答案为 \([L,R]\) 内的一个数。
当然，给出的询问不会这么巧合正好是上面那种情况的，所以我们在整体二分时需要对询问排序，当然这个后面会说。
因为答案在 \([L,R]\) 内，所以考虑找到中点 \(mid\)，然后把下标在 \([L,mid]\) 内的数加到树状数组里（事实上如果权值不大可以加权值，但这题只能使用下标，要不然空间会炸）。
然后考虑如果对于一个询问 \((l,r,k)\)，树状数组在 \([l,r]\) 内的数的数量 \(num\) 不小于 \(k\)，证明对于这个询问 \(mid\) 太大了，把他扔到数组 \(q1\) 中；否则就是 \(mid\) 太小了，于是先 \(k-num\leftarrow k\)，然后把这个询问扔到数组 \(q2\) 内。
这里说一下为什么要 \(k-num\leftarrow k\)。因为我们接下来对这类 \(mid\) 太小了的询问会单独处理，而后面统计的是在新区间内不大于他的数的数量。我们不能忽略之前比他小的数带来的贡献，所以要做这样一个操作。
然后做完这个类似于归并排序的操作后，我们把之前树状数组里的东西清空掉，然后把 \(q1,q2\) 数组内的东西放回询问数组接着递归处理（事实上就是做了个分类，然后对两类询问集训递归）。
边界情况：\(L=R\)，此时 \([l,r]\) 内的询问的答案结尾 \(val_L\)，注意不是 \(L\)，因为我们一开始用下标代替了权值。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,m,c[N],res[N];
struct node{
int id,x;
bool operator<(const node &t)const{
return x<t.x;
}
}a[N];
struct ask{
int id,l,r,k;
}q[N],q1[N],q2[N];
int lowbit(int x){
return x&-x;
}
void modify(int x,int v){
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
}
int qry(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
void solve(int l,int r,int L,int R){
if(l>r)return;
if(L==R){
for(int i=l;i<=r;i++){
res[q[i].id]=a[L].x;
}
return;
}
int mid=L+R>>1;
for(int i=L;i<=mid;i++){
modify(a[i].id,1);
}
int cnt1=0,cnt2=0;
for(int i=l;i<=r;i++){
int sum=qry(q[i].r)-qry(q[i].l-1);
if(q[i].k<=sum){
q1[++cnt1]=q[i];
}
else{
q[i].k-=sum;
q2[++cnt2]=q[i];
}
}
for(int i=L;i<=mid;i++){
modify(a[i].id,-1);
}
for(int i=1;i<=cnt1;i++){
q[i+l-1]=q1[i];
}
for(int i=1;i<=cnt2;i++){
q[i+l+cnt1-1]=q2[i];
}
solve(l,l+cnt1-1,L,mid);
solve(l+cnt1,r,mid+1,R);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].x;
a[i].id=i;
}
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r>>q[i].k;
q[i].id=i;
}
sort(a+1,a+n+1);
solve(1,m,1,n);
for(int i=1;i<=m;i++){
cout<<res[i]<<'\n';
}
return 0;
}