POJ 2104&&2761 不修改的K大数 (主席树) (二)
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);
} www.2cto.com
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;
}