UOJ Logo zzzYheng的博客

博客

UNR#8 D2T2 的一个乱搞做法

2024-09-01 23:25:12 By zzzYheng

首先考虑直接二分值域然后在每行二分有多少个小于 $lim$ 的位置可以做到 $\Theta(n\log V\log n)$ 次询问。

然后考虑整体二分,假设已知 $[L,R]$ 行的最后一个小于 $lim$ 的位置在 $[l-1,r]$ 中。令 $mid=(l+r)/2$,满足 $a_{i,mid}< lim $ 的行会递归到 $[mid+1,r]$,满足 $a_{i,mid}\ge lim$ 的行会递归到 $[l,mid-1]$。

由于 $a_{i,mid}$ 单调不减,所以可以二分出两类行的分界点。

这样每次 $\text{check}$ 的询问次数大概是 $\Theta(n)$,并且完全卡不满,因为会怎样递归跟二分的 $lim$ 有关。

然后有两个优化:

  • 记忆化:

    记忆下来每列求出过的位置,这样在二分分界点的时候可以缩小二分的区间,这个优化在 $lim$ 接近答案的时候很有用。

    这样询问次数的上界变为了 $\Theta(n\log n)$,因为如果二分到的两个 $lim$ 在所有 $a_{i,j}$ 中的排名相同,那么其实不需要任何额外的询问。

  • 剪枝:

    假设最后求出的分界点是 $res$,那么 $[L,res]$ 行的 $[l,mid]$ 位置就一定是 $ < lim$ 的了,且 $[res+1,R]$ 行的 $[mid,r]$ 位置就一定是 $\ge lim$ 的了,所以可以记录已经得到的 $< lim $ 和 $\ge lim$ 位置,如果已经可以判定出结果那就直接退出。

    并且这个优化在 $[l,r]$ 大的时候更有用,所以以 $\text{bfs}$ 的顺序去递归效果会更好。

    这个优化在 $lim$ 离答案很远的时候很有用。

但是这样会被 $\text{hack}$,但是整体二分的时候给 $mid$ 随机扰动一下就直接过了。

希望大家能把这个乱搞 X 掉(bushi

评论

zzzYheng
代码:https://uoj.ac/submission/712969

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。