Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

Codeforces GYM 103069B Rectangle Flip 2 解题报告

有一个 $n*m$ 矩形,初始全白。

现在进行 $nm$ 次操作,每次将一个格子涂黑,操作完输出有多少个子矩形里面没有黑格子。

$n,m\leq 500$

毒瘤题

最开始一共有 $\frac{n\times (n+1) \times m \times (m+1)}{4}$ 个子矩形

考虑枚举新增的不合法矩形的左右边界,算出上下边界

破防了不会了

网上看了下题解尝试理解下,和那个 DP 的悬线法差不多,我往左边枚举到第一个黑色格子,并且走的过程中一路控制上下格子保证走出来一个全白的矩形。

枚举左的同时,往右走,我们设当前的上面位于 $u$ , 下面位于 $d$,那么我们这组 $(l,r)$ 的减去矩形个数就为 $(x - u + 1) \times (d - x + 1)$,结合图片理解

![[Pasted image 20210628153950.png]]

这里,我们能确定的就是中间的绿色这一条矩形是新的不合法矩形,中间统计的过程是 $O(nm)$ 的。

那么问题来了,这个题怎么看怎么都像是 $O(n^4)$ 的,为什么能过?

这个过程实际上是类似树形 DP 的过程,我们合并的一组 $(l,r)$ 实际上只会在 LCA 处被合并一次,所以就变成了严格的 $O(n^2)$,多带一个 $n$ 也就得到了我们正确的时间复杂度。

时间复杂度 $O(n^3)$

Code