不知道说啥。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=(2e5)+,maxm=maxn;
int N,M,K,num_treenode=,root[maxn],X,B[maxn],num=,L,R,ans,F[maxn];
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
struct Tree{
int l,r,data,ls,rs;
}t[(maxn<<)+maxm*];
struct Num{
int id,data;
}A[maxn];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;
if(l==r)return;
int mid=(l+r)>>;
Build(t[x].ls=++num_treenode,l,mid); Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline bool cmp(const Num&a,const Num&b){return(a.data<b.data);}
inline void Update(int u,int x,int q){
int l,r,mid;
t[x].l=l=t[u].l;t[x].r=r=t[u].r;mid=(l+r)>>;
if(l==r&&l==q){t[x].data=t[u].data+; return;}
if(q<=mid){t[x].rs=t[u].rs; Update(t[u].ls,t[x].ls=++num_treenode,q);}
else{t[x].ls=t[u].ls; Update(t[u].rs,t[x].rs=++num_treenode,q);}
t[x].data=t[t[x].ls].data+t[t[x].rs].data;
return;
}
inline int Query(int r1,int r2,int k){
int l=t[r1].l,r=t[r1].r,ls=t[r1].ls,rs=t[r1].rs,ls_=t[r2].ls,rs_=t[r2].rs,sum=t[ls_].data-t[ls].data;
if(l==r)return l;
if(k<=sum)return Query(ls,ls_,k);else return Query(rs,rs_,k-sum);
}
int main(){
N=rd();M=rd();
root[]=++num_treenode;
Build(num_treenode,,N);
for(int i=;i<=N;i++){
A[i].data=rd();
A[i].id=i;
}
sort(A+,A+N+,cmp);
A[].data=int(1e9);
for(int i=;i<=N;i++)
if(A[i].data!=A[i-].data) B[A[i].id]=++num,F[num]=A[i].data;else B[A[i].id]=num;//find是离散化后的数对应的原数是什么
for(int i=;i<=N;i++)Update(root[i-],root[i]=++num_treenode,B[i]);
while(M--){
L=rd();R=rd();K=rd();
ans=Query(root[L-],root[R],K);
printf("%d\n",F[ans]);
}
return ;
}
By:AlenaNuna