else
s1=cnt[deep][l-1];
s2=cnt[deep][r]-s1; //s2为[l,r]中分到左子树的个数
if(k<=s2) //左子树的数量大于k,递归左子树
return query(2*step,tree[step].left+s1,tree[step].left+s1+s2-1,k,deep+1);
int b1=l-1-tree[step].left+1-s1; //b1为[tree[step].left,l-1]中分到右子树的个数
int b2=r-l+1-s2; //b2为[l,r]中分到右子树的个数
return query(2*step+1,tree[step].mid+1+b1,tree[step].mid+1+b1+b2-1,k-s2,deep+1);
}
int main(){;
while(scanf("%d%d",&n,&q)!=EOF){
for(int i=1;i<=n;i++){
sa[i]=num[1][i];
}
sort(sa+1,sa+n+1);
bulid(1,1,n,1);
while(q--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(1,l,r,k,1));
}
}
return 0;
}
作者：ACM_cxlove