模板题，题意是求区间第k大，套一下主席树模板或者划分树模板即可（屯板子）
代码如下：
主席树：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int rt[maxn<<5];
int sum[maxn<<5];
int ls[maxn<<5],rs[maxn<<5];
int tot;
int p;
void build(int lef,int rig,int& root) //其实就是一个为各节点分配id的过程
{
root=++tot;
if(lef==rig) return ;
int mid=lef+(rig-lef)/2;
build(lef,mid,ls[root]);
build(mid+1,rig,rs[root]);
}
int update(int lef,int rig,int root)
{
int root_=++tot; //建一棵新树
ls[root_]=ls[root];
rs[root_]=rs[root];
sum[root_]=sum[root]+1;
if(lef==rig) return root_;
int mid=lef+(rig-lef)/2;
if(p<=mid){
ls[root_]=update(lef,mid,ls[root_]); //如果修改点在左儿子，就新建一个左儿子
}else{
rs[root_]=update(mid+1,rig,rs[root_]); //如果修改点在右儿子，就新建一个右儿子
}
return root_;
}
int query(int u,int v,int lef,int rig,int k)
{
int ans=0;
int mid=lef+(rig-lef)/2;
int x=sum[ls[v]]-sum[ls[u]];
if(lef==rig) return lef;
if(x>=k){
ans=query(ls[u],ls[v],lef,mid,k);
}else{
ans=query(rs[u],rs[v],mid+1,rig,k-x);
}
return ans;
}
int arr[maxn];
int lisan[maxn];
int main()
{
tot=0;
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>arr[i],lisan[i]=arr[i];
sort(lisan+1,lisan+1+n);
int len=unique(lisan+1,lisan+1+n)-lisan-1;
build(1,len,rt[0]);
for(int i=1;i<=n;i++){
p=lower_bound(lisan+1,lisan+1+len,arr[i])-lisan;
rt[i]=update(1,len,rt[i-1]);
}
int ans=0;
for(int i=0;i<m;i++){
int L,R,k;cin>>L>>R>>k;
ans=query(rt[L-1],rt[R],1,len,k);
cout<<lisan[ans]<<"\n";
}
return 0;
}划分树：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+50;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int tree[20][maxn];
int to_lef[20][maxn];
int sorted[maxn];
void build(int lef,int rig,int lev)
{
if(lef==rig) return ;
int mid=lef+(rig-lef)/2;
int sup=mid-lef+1;
for(int i=lef;i<=rig;i++){
if(tree[lev][i]<sorted[mid]){
sup--;
}
}
int sublef=lef;int subrig=mid+1;
for(int i=lef;i<=rig;i++){
if(i==lef){
to_lef[lev][i]=0;
}else{
to_lef[lev][i]=to_lef[lev][i-1];
}
if(tree[lev][i]<sorted[mid]||tree[lev][i]==sorted[mid]&&sup>0){
tree[lev+1][sublef++]=tree[lev][i];
to_lef[lev][i]++;
if(tree[lev][i]==sorted[mid]) sup--;
}else{
tree[lev+1][subrig++]=tree[lev][i];
}
}
build(lef,mid,lev+1);
build(mid+1,rig,lev+1);
}
int query(int lev,int lef,int rig,int L,int R,int k)
{
int mid=lef+(rig-lef)/2;
if(L==R) return tree[lev][L];
int lef_,tolef;
if(L==lef){
lef_=0;tolef=to_lef[lev][R];
}else{
lef_=to_lef[lev][L-1];
tolef=to_lef[lev][R]-lef_;
}
if(k<=tolef){
int tmp_lef=lef+lef_;
int tmp_rig=lef+lef_+tolef-1;
return query(lev+1,lef,mid,tmp_lef,tmp_rig,k);
}else{
int tmp_lef=mid+L-lef-lef_+1;
int tmp_rig=mid+R-lef-lef_-tolef+1;
return query(lev+1,mid+1,rig,tmp_lef,tmp_rig,k-tolef);
}
}
int main()
{
int n,m;scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&sorted[i]);
tree[0][i]=sorted[i];
}
sort(sorted+1,sorted+1+n);
build(1,n,0);
for(int i=0;i<m;i++){
int x,y,k;scanf("%d %d %d",&x,&y,&k);
int ans=query(0,1,n,x,y,k);
printf("%d\n",ans);
}
return 0;
}