UOJ Logo PEKKA_l的博客

博客

标签

UNR #8 D2T2 另解

2024-07-14 21:47:56 By PEKKA_l

题解

注意到 【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),我觉得换成斜向分组的方式可以通过,有没有大神试试写一下啊(?)

共 1 篇博客