Hints of sd0061

题目链接

题意

用给的随机函数可以得到数列$a$，$m$次查询，问第$b_{i}$小的数字。

思路

这道题要线性第$k$小，肯定是不能排序的。
一个思路是手写快排，然后将所有询问一起二分掉，比较卡的做法。

其实这是个套路题
使用STL < algorithm >中的

nth_element(A, A + k, A + n)

可以在线性时间找到第k大，此题还需要一点小trick，可以先将询问排序，然后每次将排序范围缩小，可以减小枚举量。