记录编号	454508	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.001 s
提交时间	2017-09-29 07:22:04	内存使用	18.96 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
//#define mem(x) memset((x),0,sizeof(x))
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
int T;
int n,m;
int a[100005],num[100005];
int cnt,size;
int rt[2000005],sum[2000005],lch[2000005],rch[2000005];
inline void build(int &x,int l,int r){
    x=++cnt;
    sum[x]=0;
    if(l==r){
        lch[x]=rch[x]=0;
        return;
    }
    int mid((l+r)>>1);
    build(lch[x],l,mid);
    build(rch[x],mid+1,r);
}
inline void update(int &x,int las,int pos,int l,int r){
    x=++cnt;
    lch[x]=lch[las];
    rch[x]=rch[las];
    sum[x]=sum[las]+1;
    if(l==r)
        return;
    int mid((l+r)>>1);
    if(pos<=mid)
        update(lch[x],lch[las],pos,l,mid);
    else
        update(rch[x],rch[las],pos,mid+1,r);
}
inline int query(int ll,int rr,int l,int r,int k){
    if(l==r)
        return l;
    int mid((l+r)>>1);
    int cnt(sum[lch[rr]]-sum[lch[ll]]);
    if(k<=cnt)
        return query(lch[ll],lch[rr],l,mid,k);
    return query(rch[ll],rch[rr],mid+1,r,k-cnt);
}
inline int gg(){
    freopen("kth.in","r",stdin);
    freopen("kth.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        num[i]=a[i]=read();
    sort(num+1,num+n+1);
    size=unique(num+1,num+n+1)-num-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(num+1,num+size+1,a[i])-num;
    build(rt[0],1,size);
    for(int i=1;i<=n;++i)
        update(rt[i],rt[i-1],a[i],1,size);
    for(int i=1;i<=m;++i){
        int l(read()),r(read()),k(read());
        int ans(query(rt[l-1],rt[r],1,size,k));
        printf("%d\n",num[ans]);
    }
}
int K(gg());
int main(){;}