算法理解
建议结合OIwiki和本人文字食用
本质上离线询问，然后对询问的答案进行二分，根据二分的结果（满足？/不满足？）对问题根据询问进行分治（类似于CDQ分治？），即对于所有的询问同时进行二分
T1：
考虑单个问题 \((x,y,k)\) 的 \(check\)：
我们可以在序列的值域 \([l,r]\) 上二分, 然后判断在 \([l,r]\) 中数的序号在 \([x,y]\) 中的个数（大于？/小于？）k
可以用树状数组维护序号
多个问题怎么办？
多个问题全都再重新加一遍树状数组显然不优，那我们就同时进行所有询问的二分，把二分到同一个值域区间 \([l,r]\) 的询问同时进行树状数组查询，然后再根据二分结果进行分治递归
因为值域递归并且每一层都会递归到，递归深度为 \(O(log(值域))\) 并且再加上树状数组复杂度，过不了
可以剪枝水过
if(q1.size()) solve(l,mid,a1,q1);
if(q2.size()) solve(mid+1,r,a2,q2);
正确优化方法：离散化值域
总复杂度 \(O((n+m)log^2n)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct num{int x,p;
};
struct query{int x,y,k,i;void change(int x){k-=x;}
};
int n,m,mxnum;
int tr[N],ans[N],c[N],b[N];
map<int,int>mp;
int lowbit(int x){return x&(-x);
}
void merge(int x,int z){for(;x<=n;x+=lowbit(x)){tr[x]+=z;}
}
int ask(int x){int res=0;for(;x;x-=lowbit(x)){res+=tr[x];}return res;
}
void solve(int l,int r,vector<num>a,vector<query>q){if(l==r){for(auto i:q) ans[i.i]=l;return;}int mid=(l+r)>>1;vector<num>a1,a2;for(auto i:a){if(i.x<=mid){a1.push_back(i);merge(i.p,1);}else{a2.push_back(i);}}vector<query>q1,q2;for(auto i:q){int res=ask(i.y)-ask(i.x-1);// printf("%d %d %d %d %d %d\n",i.x,i.y,i.k,res,l,r);if(i.k<=res) q1.push_back(i);else i.change(res),q2.push_back(i);}for(auto i:a){if(i.x<=mid){merge(i.p,-1);}}solve(l,mid,a1,q1);solve(mid+1,r,a2,q2);
}
int main(){scanf("%d%d",&n,&m);vector<num>a;vector<query>q;for(int i=1;i<=n;i++){scanf("%d",&c[i]);b[i]=c[i];}sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;for(int i=1;i<=len;i++){mp[b[i]]=i;}for(int i=1;i<=n;i++){c[i]=mp[c[i]];a.push_back({c[i],i});}for(int i=1;i<=m;i++){int l,r,k;scanf("%d%d%d",&l,&r,&k);q.push_back({l,r,k,i});}solve(1,n,a,q);for(int i=1;i<=m;i++){printf("%d\n",b[ans[i]]);}
}