m次k小值复杂度nlogm–上海科技大学2024年考研数据结构的某个题的第二问

前言：

当时场上没想出来，我感觉我很容易算错时间复杂度，22年的icpc济南，那道矩阵取模的题也是因为当时时间复杂度算错了结果没写。主要原因应该还是太依赖感觉了。

题目描述：

这个题的第一问是无序序列求k小值。快速选择时间空间都是o(n)，显然没有亚线性的算法。

第二问：

有m次询问，每次询问$k_i$小值要求空间复杂度不变（还是o(n)）要求时间复杂度是o(nlogm)注意m是询问次数。

思路：

很显然要考虑离线

首先发现m次询问可以先排个序，感觉很有用但好像也没什么用（当时场上想到这里就开始想用平衡树，treap之类的了）

考虑一下快速选择的平均复杂度为什么是o(n)很显然平均情况下它每层递归的复杂度应该是$n/(2^i)$，等比级数求和即可。
$$
S(n) = \sum_{i=0}^{inf} \frac{n}{2^i}=2n
$$
延续一下这个思想，我们发现在快速选择的时候，每当选定一个轴，做完一轮分组以后，轴的位置可能产生移动。在快速选择中，我们会抛弃此时的轴的左边全部或者右边全部。

考虑同时处理m次询问。我们首先对m次询问进行排序，然后处理中间的那个询问，假设是第p个询问。发现当我们通过快速选择法找到中间那个询问的答案（假设是$k_i$，下标为h）以后此时的数组里，第1~p-1个询问的答案都会在$k_i$的左边，第p+1~m个询问的答案都在$k_i$的右边。

那么我们就得到了一个子问题，假设数组是a，下标从1开始。也就是在a[1]~a[h-1]中处理询问1~p-1和在a[h+1]~a[n]中处理询问p+1~m。这个子问题可以通过遍历1/2个序列得到答案并获得另外两个子问题。同理，每层子问题都可以通过遍历$1/{2^{层数-1}}$个序列获得答案并得到两个子问题。

递归求解即可。