题解 ARC179E Rectangle Concatenation

· · 题解

一个好想好写的 O(N) 做法。

先思考 O(N^2) 怎么做。枚举一个 l，设 S_r 为 [l,r] 的面积和，发现以 r 为右端点只可能有两种合法的矩形。

考虑递推，设 f_{r,0/1} 表示以 r 为右端点能不能横着或竖着放。有递推式：

f_{r,0}=(f_{r-1,0}\land x_r=x_{r-1})\lor(f_{r-1,1}\land x_r=\frac{S_{r-1}}{y_{r-1}}) f_{r,1}=(f_{r-1,1}\land y_r=y_{r-1})\lor(f_{r-1,0}\land y_r=\frac{S_{r-1}}{x_{r-1}})

考虑优化。

我们转而枚举 r，分别维护 f_{r,0} 合法和 f_{r,1} 合法的 l。发现两个式子的第一部分要么清空要么继承，而第二部分对 S 有唯一的限制，因此只会涉及到一个地方的值。

所以总的修改量是 O(N) 的，可以直接用数组模拟，暴力操作维护出两个集合并的大小。

此外，还需要用 hash 表找到第二部分修改的位置。

总复杂度 O(N)。