先咕一下，闲下来写。

是我场上写的做法，只不过场上我以为它的复杂度是 $O(n \log n)$ 状物。

中间复杂度分析的部分有大量我的扯淡，请在看中间的分析之前先跳到最后查看正确的复杂度分析。

来写一下。

由于我不会 SMAWK，所以只能随机二分，自然询问次数为 $O(n\log n)$。

考察瓶颈所在的位置：二分提供 $O(\log n)$，双指针提供 $O(n)$。由于二分显然不可能被继续优化，考察如何减少双指针的次数。我的想法是设置步长 $s$，每一次指针移动的时候，相比于每次移动 $1$ 个位置，我们可以每次移动 $s$ 个位置。

这可能会带来误差，考察误差的影响。形象的思考带步长的双指针的过程。普通双指针实际上是找到了一个分割线/轮廓线，使得左上角是 $\leq mid$ 的数，右下角是 $> mid$ 的数。带步长的双指针找到的轮廓线是对这个轮廓线的一个粗略近似，但是它相比原轮廓线的误差不会超过步长 $s$。

那么我们二分再往两边递归的时候，如果想往左上递归，就将轮廓线往右下平移 $s$ 个位置，想往右下递归，就将轮廓线往左上平移 $s$ 个位置。这样所有当前可能成为第 $k$ 大的位置就仍然会被包含在待确定的区域中。

分析一下这个东西的询问次数。

我场上认为这个东西仍然是 $O(n\log n)$ 的，没有什么实质优化，所以一直在尝试调整步长 $s$ 并对拍。现在可以仔细分析一下询问次数了。下面的分析过程不太严谨，但是感性理解足够了。

设 $f(x)$ 表示当前待确定区域的左上到右下的斜向宽度（这里默认左下到右上方向的宽度为 $n$，显然不可能超过这个值）为 $x$ 的时候需要的询问次数。设步长为 $s$，有：

$$ f(x)=\min_{s} f\left(\frac{x}{2}+s\right)+O\left(\frac{n}{s}\right) $$

由于是随机二分，所以实际应该是一个概率分布，但是我正在感性理解，于是当成 $x/2$ 计算了。取 $s=\log x$，进行 $\log x$ 轮，由于 $s$ 远小于 $x$，暂时忽略这个 $f(x/2+s)$ 中的 $s$。那么有粗略的递推式：

$$ f(x)=f(\log x)+O(n) $$

然后大概就能得出 $f(n)=O(n\log^{*}n)$ 了。

虽然忽略 $s$ 这个事情看上去就不严谨，但是感性理解大概能得到一个这样的结果。然后这里不一定取到了下界，所以可能还会更优。

没有分析复杂度的常数，因为这东西本来就复杂度不优。并且我分析不明白，就这样。

感觉分析其实可能是错的，如果每一步都取 $s=\log x$，且忽略 $s$ 的话，只能得出：

$$ f(x)=f\left(\frac{x}{2}\right)+O\left(\frac{n}{\log x}\right) $$

然后这个解出来是 $f(x)=x\log \log x$。

请懂的人教我一下。@monstersqwq 教我一下谢谢。

其实是线性的，取 $s=x/2$，感谢咋克。

仔细分析各种乱七八糟的东西，最后可以得到 $15.5n$ 的复杂度上界。哈哈，没有任何意义。