ARC081D Flip and Rectangles

题意：给出一个 的 矩阵。

每次操作可以将一行或一列取反，可以进行任意多次操作，问矩阵中全 矩形面积的最大值。

，时限 。

---

首先考虑如何判定一个矩形经过操作能否变为全 。

先观察一些性质：

• 若某个矩形能被操作为全 ，那么其任意子矩形也一定可以。

• 行列任意交换不影响某个矩形是否能变为全 。

任选位置 ，若 则将整个矩形取反，这样总有 。

先查看第 行和第 列，若某个数为 ，则翻转对应 行/列。

在这之后，若做其他操作，则第 行和第 列必被破坏。所以不能进一步操作，检查此时矩阵是否全黑即可。

这等价于，对于位置 （），检查 的异或值是否为 。

也即 的异或值是否为 。

由于 也是任选的，我们得到一条性质 ： 任意一个子矩形的四个角的异或和为 。

这同时也是充要条件。

在转化充要条件时，判定算法可能是构造性的。此时要尽量多想“有没有其他方法也可以完成构造？”，以得到更多性质。

比方说，在本题中，若直接选择第一行第一列开始构造（而不是任意的 ）就很难得到这个性质。

该条件依然难以维护，考虑进行简化：能否只考虑一小部分矩形的约束呢？

条件可以看作若干异或方程组，线性相关的方程组显然是无用的。

略微手玩方程之间的线性相关模式后，可以发现，只需要考虑所有的 矩形，因为更大的矩形的四个角都可以用内部所有的 矩形异或出来。

于是，对每个 矩形，查看内部是否有奇数个 。若是，则称为坏矩形。

若一个大矩形包含了坏矩形，则无法变为全 ，反之可以。

至此，我们将原问题转化为了最大全 矩形问题。

（注意，长或宽为 的矩形总是好的）

这是经典问题，这里用悬线法解决。

复杂度 。