记录编号	432668	评测结果	AAAAAAAAAA
题目名称	930.[河南省队2012] 找第k小的数	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.599 s
提交时间	2017-08-03 17:22:23	内存使用	24.56 MiB

#pragma GCC optimize("O3")
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 100001
namespace FIFO 
{
    char ch,B[1<<20],*S=B,*T=B;
    #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
    #define isd(c) (c>='0'&&c<='9')
    int aa,bb;int F(){
        while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
        while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
    }
}
#define gi FIFO::F()
inline int read()
{
	char s=getchar();
	int a=0;
	while(s<'0'||s>'9')
		s=getchar();
	while(s>='0'&&s<='9')
	{
		a=(a<<1)+(a<<3)+s-'0';
		s=getchar();
	}
	return a;
}
struct tree
{
    int lc,rc,sum;
}tree[maxn*19];
int n,m,t;
void build(int &num,int &x,int l,int r)
{
    tree[t++]=tree[x];
    x=t-1;
    ++tree[x].sum;
    if(l==r)
        return ;
    int mid=l+r>>1;
    if(num<=mid)
        build(num,tree[x].lc,l,mid);
    else
        build(num,tree[x].rc,mid+1,r);
}
int query(int i,int j,int k,int l,int r)
{
    if(l==r)    
        return l;
    int cnt=tree[tree[j].lc].sum-tree[tree[i].lc].sum;
    int mid=l+r>>1;
    if(k<=cnt)
        return query(tree[i].lc,tree[j].lc,k,l,mid);
    return query(tree[i].rc,tree[j].rc,k-cnt,mid+1,r);
}
struct AAA
{
    int x,id;
    bool operator < (const AAA &BBB) const
    {
        return x<BBB.x;
    }    
}a[maxn];
int root[maxn],order[maxn];
int main()
{
    freopen("kth.in","r",stdin);
    freopen("kth.out","w",stdout);
    int x,y,z,i;
    tree[0].lc=tree[0].rc=tree[0].sum=0;
    root[0]=0;
    n=gi;
    m=gi;
    for(i=1;i<=n;++i)
    {
        a[i].x=gi;
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        order[a[i].id]=i;
    t=1;
    for(i=1;i<=n;++i)
    {
        root[i]=root[i-1];
        build(order[i],root[i],1,n); 
    }
    for(i=1;i<=m;++i)
    {
        x=gi;
        y=gi;
        z=gi;
        printf("%d\n",a[query(root[x-1],root[y],z,1,n)].x);
    }
}