记录编号	600086	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	4.410 s
提交时间	2025-04-15 20:05:14	内存使用	71.16 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[200005],t,tt,V=1e9,xx,yy,zz,rt[200005];
struct nd{
    long long l,r,sm;
}tr[10000005];
long long add(long long pp,long long p,long long l,long long r,long long x,long long y){
    if(!p) p=++t;
    tr[p].l=tr[pp].l,tr[p].r=tr[pp].r,tr[p].sm=tr[pp].sm+y;
    if(l==r) return p;
    long long md=(l+r)>>1;
    if(x<=md) tr[p].l=add(tr[pp].l,0,l,md,x,y);
    else tr[p].r=add(tr[pp].r,0,md+1,r,x,y);
    return p;
}
long long sum(long long p,long long l,long long r,long long x,long long y){
    if(!p) return 0;
    if(x<=l&&r<=y) return tr[p].sm;
    long long s=0,md=(l+r)>>1;
    if(x<=md) s+=sum(tr[p].l,l,md,x,y);
    if(md+1<=y) s+=sum(tr[p].r,md+1,r,x,y);
    return s;
}
long long fd(long long pp,long long p,long long l,long long r,long long rk){
    if(l==r) return l;
    long long md=(l+r)>>1;
    if(!tr[p].r||tr[tr[p].l].sm-tr[tr[pp].l].sm>=rk) return fd(tr[pp].l,tr[p].l,l,md,rk);
    return fd(tr[pp].r,tr[p].r,md+1,r,rk-tr[tr[p].l].sm+tr[tr[pp].l].sm);
}
int main(){
    freopen("kthnumber.in","r",stdin);
    freopen("kthnumber.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=V,rt[i]=add(rt[i-1],++t,0,V+V,a[i],1);
    while(m--){
        cin>>xx>>yy>>zz;
        cout<<fd(rt[xx-1],rt[yy],0,V+V,zz)-V<<"\n";
    }
    return 0;
}