记录编号	600121	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	3.547 s
提交时间	2025-04-15 22:19:29	内存使用	77.81 MiB

#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=200010;
struct Seg
{
    int l,r,val;
    Seg(){l=r=val=0;}
    Seg(int ll,int rr,int vall){l=ll,r=rr,val=vall;}
}a[N<<5];
int n,m,q,jsq;
int s[N],ys[N],rt[N];
int build(int l,int r)
{
    jsq++;
    if(l==r) return jsq;
    int mid=(l+r)/2,ls=jsq;
    a[ls]=(Seg){build(l,mid),build(mid+1,r),0};
    return ls;
}
int update(int w,int l,int r,int p)
{
    jsq++;a[jsq]=(Seg){a[p].l,a[p].r,a[p].val+1};
    if(l==r) return jsq;
    int mid=(l+r)/2,ls=jsq;
    if(w<=mid) a[ls].l=update(w,l,mid,a[p].l);
    else a[ls].r=update(w,mid+1,r,a[p].r);
    return ls;
}
int query(int p1,int p2,int l,int r,int rk)
{
    if(l>=r) return l;
    int ls=a[a[p2].l].val-a[a[p1].l].val,mid=(l+r)/2;
    if(rk<=ls) return query(a[p1].l,a[p2].l,l,mid,rk);
    return query(a[p1].r,a[p2].r,mid+1,r,rk-ls);
}
int main()
{
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
    n=re();q=re();
    for(int i=1;i<=n;i++) ys[i]=s[i]=re();
    sort(ys+1,ys+1+n);
    m=unique(ys+1,ys+1+n)-(ys+1);
    rt[0]=build(1,m);
    for(int i=1;i<=n;i++) rt[i]=update(lower_bound(ys+1,ys+1+m,s[i])-ys,1,m,rt[i-1]);
    for(int i=1,l,r,k;i<=q;i++)
    {
        l=re();r=re();k=re();
        printf("%d\n",ys[query(rt[l-1],rt[r],1,m,k)]);
    }
    return 0;
}