记录编号	414335	评测结果	AAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-06-14 07:39:40	内存使用	6.01 MiB

//主席树，权值线段树，每个线段存的是这个区间大小的数当前出现的次数 
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int a[N],num[N],n,m,cnt=0,root[N];
int ql,qr,k;
struct Tree
{
    int l,r,sum;
}tree[N*4];
void build(int &o,int l,int r)
{
     o=++cnt;
     tree[o].sum=0;
     if(l==r) return ;
     int m=(l+r)/2;
     build(tree[o].l,l,m);
     build(tree[o].r,m+1,r);
}
void update(int p,int &o,int l,int r,int x)
{
     o=++cnt;
     tree[o]=tree[p];
     tree[o].sum++;
     if(l==r) return ;
     int m=(l+r)/2;
     if(x<=m)
       update(tree[p].l,tree[o].l,l,m,x);
     else
       update(tree[p].r,tree[o].r,m+1,r,x);
}
int query(int p,int o,int l,int r,int x)
{
     if(l==r) return l;
     int m=(l+r)/2;
     int ln=tree[tree[o].l].sum-tree[tree[p].l].sum;
     if(x<=ln) return query(tree[p].l,tree[o].l,l,m,x);
     else return query(tree[p].r,tree[o].r,m+1,r,x-ln);
}
int main()
{
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
      num[i]=a[i];
    }
    sort(num+1,num+n+1);
    int num_cnt=unique(num+1,num+n+1)-num-1;  //去重 
    build(root[0],1,num_cnt);  //建空树
    //for(int i=1;i<=num_cnt;i++)
      //printf("%d ",num[i]); 
    //printf("\n");
    for(int i=1;i<=n;i++)
    {
      int x=lower_bound(num+1,num+num_cnt+1,a[i])-num;  //离散 
      //printf("%d  %d\n",a[i],x);
      update(root[i-1],root[i],1,num_cnt,x);
    }
    for(int i=1;i<=m;i++)
    {
      scanf("%d%d%d",&ql,&qr,&k);
      int x=query(root[ql-1],root[qr],1,num_cnt,k);
      printf("%d\n",num[x]);
    }
    //while(1);
}