题解

注意到 【UR #4】元旦激光炮说明了这样一件事情，假如有 $B$ 个内部已升序排序的序列 $x_{1,i},x_{2,i},\dots,x_{B,i}$，则对于使得 $x_{j,\lfloor k/B \rfloor}$ 最小的 $j$ 来说，$x_{j,1},x_{j,2},\dots,x_{j,\lfloor k/B \rfloor}$ 一定都不是全局第 $k$ 小，这样就可以不断令 $k\gets \lfloor k/B \rfloor$。

回到本题，我们考虑斜向分块。把矩阵切成若干形状大约是 $B\times B$ 的矩形，然后就可以按斜对角线方向分成 $O(\frac{n}{B})$ 组，使得每组内部的矩形都存在偏序关系。此时把每组看成上文所说的一个序列，则这 $\frac{n}{B}$ 个序列每一个的第 $B\times B$ 小元素都可以 $1$ 次询问直接问出（小矩形的右下角），当 $k>O(nB)$ 时套用以上结论可以在 $O(\frac{n}{B})+O(q)$ 次询问的代价内令 $k\gets k-q\times B\times B$。

直接把分块递归地做下去，由于两次的块长最好成倍数关系，我们令 $B_i=n\times \frac{1}{2^i}$，则得到总询问次数 $O(\sum O(\frac{n}{2^i}))=O(n)$，常数应当不太大（？）

分析一下常数，如有错误请指出：

首先斜向分组虽然会分出 $\frac{2n}{B}$ 组，但每个时刻需要考虑的组只有至多 $\frac{n}{B}$ 个，因为与分界线没有两条邻边的块暂时不会是最小值（官方题解：如果 $(x-1,y)$ 和 $(x,y-1)$ 还没被选进前 $k$ 小，$(x,y)$ 就暂时不会被选）。所以对每个 $B$ 的预处理至多用 $\frac{n}{B}$ 次询问。

然后事实上每次用 $B$ 可以把 $k$ 缩减到 $nB-\frac{n}{B}$ 以内（有 $\frac{n}{B}$ 个序列），因此缩减 $k$ 这一部分至多需要 $\frac{nB+\frac{n}{2B}}{B^2}=\frac{n}{B}+\frac{n}{2B^3}$ 次询问。那么好像分析总的询问次数至多 $\sum\limits_{i\geq 0}\frac{n}{2^i}+\sum\limits_{i\geq 0}\frac{n}{2^i}+\sum\limits_{i\geq 0}\frac{n}{2^{3i+1}}<4n+\frac{9}{16}n=4.5625n$，好像比官方题解分析得更优？

upd：对不起，以上分析假完了。用 $B$ 只能缩减到 $(2n-1)B-\frac{2n}{B}+1$，因此算出来会爆，不过我还是觉得有办法使这种做法通过本题。

虽然由于 $200000$ 不是 $2$ 的幂，实际次数上限会略有一些偏差，但应该差不太多（？）这有道理吗？

代码

感觉斜向分块的实现有些困难，我赛时实现了完全没有正确性的横向迭代分块，并且询问次数多乘了 $\log\log n$（当时设块长 $B_i=n^{2^{-i}}$），但是依然获得了八十分，提交记录如下：https://uoj.ac/submission/704132

赛后改了块长，虽然理所应当地 WA 了但询问次数貌似很对，https://uoj.ac/submission/704892

综上所述（x），我觉得换成斜向分组的方式可以通过，有没有大神试试写一下啊（？）