转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目：查询区间的K小数，不修改
继续跟着岛娘，适妞学习主席树~~~~
离散化。
以每个位置为起点，建立一棵主席树，保存后缀区间的情况。
由于每个位置的主席树其实是构造是完全相同的
在查询的时候，便可以直接相减，T[l]-T[r+1]便是[l,r]区间的情况。
依旧是从后往前更新，建立主席树。。
在前一个位置的基础上，新建一棵树，在当前位置更新
int n,q,m,tot;
int a[N],t[N];
int T[M],lson[M],rson[M],c[M];
void Init_hash(){
for(int i=1;i<=n;i++)
t[i]=a[i];
sort(t+1,t+1+n);
m=unique(t+1,t+1+n)-t-1;
}
int bulid(int l,int r){
int root=tot++;
c[root]=0;
if(l!=r){
int mid=(l+r)>>1;
lson[root]=bulid(l,mid);
rson[root]=bulid(mid+1,r);
}
return root;
}
int hash(int x){
return lower_bound(t+1,t+1+m,x)-t;
}
int update(int root,int pos,int val){
int newroot=tot++,tmp=newroot;
c[newroot]=c[root]+val;
int l=1,r=m;
while(l<r){
int mid=(l+r)>>1;
//cout<<l<<" "<<r<<endl;
if(pos<=mid){
lson[newroot]=tot++;rson[newroot]=rson[root];
newroot=lson[newroot];root=lson[root];
r=mid;
}
else{
rson[newroot]=tot++;lson[newroot]=lson[root];
newroot=rson[newroot];root=rson[root];
l=mid+1;
}
c[newroot]=c[root]+val;
}
return tmp;
}
int query(int left_root,int right_root,int k){
int l=1,r=m;
while(l<r){
int mid=(l+r)>>1;
if(c[lson[left_root]]-c[lson[right_root]]>=k){
r=mid;
left_root=lson[left_root];
right_root=lson[right_root];
}
else{
l=mid+1;
k-=c[lson[left_root]]-c[lson[right_root]];
left_root=rson[left_root];
right_root=rson[right_root];
}
}
return l;
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
tot=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
Init_hash();
T[n+1]=bulid(1,m);
for(int i=n;i;i--){
int pos=hash(a[i]);
T[i]=update(T[i+1],pos,1);
}
while(q--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",t[query(T[l],T[r+1],k)]);
}
}
return 0;
}