有一个 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