回顾了一下主席树的板子
#include <cstdio>
#include <algorithm>
#define ls t[id].ch[0]
#define rs t[id].ch[1]
#define ols t[las].ch[0]
#define ors t[las].ch[1]
#define mid (l+r>>1)
const int N=200010;
struct sor
{
int i,dat;
bool friend operator <(sor n1,sor n2)
{
return n1.dat<n2.dat;
}
}a[N];
struct node
{
int ch[2],dat;
}t[N*30];
int tot=0;
int New(int dat)
{
t[++tot].dat=dat;
return tot;
}
int root[N],dat[N];
int build(int id,int l,int r)//建时间为0的树供使用
{
if(!id) id=New(0);
if(l==r) return id;
ls=build(ls,l,mid);
rs=build(rs,mid+1,r);
return id;
}
int rebuild(int id,int l,int r,int pos,int las)
{
if(!id) id=New(1);
if(l==r) return id;
if(pos<=mid)
{
ls=rebuild(ls,l,mid,pos,ols);
rs=ors;
}
else
{
ls=ols;
rs=rebuild(rs,mid+1,r,pos,ors);
}
t[id].dat=t[ls].dat+t[rs].dat;
return id;
}
int query(int id,int l,int r,int k,int las)
{
if(l==r) return l;
if(t[ols].dat-t[ls].dat>=k) return query(ls,l,mid,k,ols);
else return query(rs,mid+1,r,k-t[ols].dat+t[ls].dat,ors);
}
int main()
{
int n,m,k,l,r;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].dat);
a[i].i=i;
}
std::sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
dat[a[i].i]=i;
root[0]=build(0,1,n);
for(int i=1;i<=n;i++)
root[i]=rebuild(0,1,n,dat[i],root[i-1]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d
",a[query(root[l-1],1,n,k,root[r])].dat);
}
return 0;
}