【旧事重提】Empty Rectangles

WeLikeStudying · 2022-03-15 15:05:40 · 题解

• 我最近发现很多所谓的唯一解法都是二分或分治的题目可以不需要二分或分治 qwq，或许我们可以专门研究一下这类问题？
• 比如这题，这题和这题。

题意

• 例题。
• 有一个 n\times m 的 01 矩阵，询问内部有多少个子矩阵恰好有 k 个 1。

分析

• 为了形象化，用黑点代表 1，白点代表 0。
• 考虑到 k\le 6，考虑暴力枚举上下边界暴力算 k。
• 我们重点关注黑点，然后我们发现黑点的数目太多了，O(nm) 的，光枚举直接爆炸。
• 所以我们发挥人类智慧，发现若多于 k+1 个点都在同一列上，则这一列上可以只保留最上面的 k+1 个点，所以黑点的数目被降到了 O(mk)，允许我们构思与黑点个数有关的算法。
• 我们发现黑点分隔开了一些区间，而我们需要统计的就是间隔恰好为 k 的区间两两的乘积（还有大于 k 的黑点形成的区间），我们将这种关系比作连边，那么如果一个区间被断开了，或者它内部的数的个数加 1，只会影响它向左和向右的最多 k 个区间（的贡献），暴力算再暴力更新即可，与这题很类似。
• 然后我们用 \text{set} 维护所有的区间，时间复杂度即 O(n^2+nmk^2\log m)。
• 当然，如果您发现这个过程可以逆过来搞把断裂区间变为合并区间，而且链表可以建成关于黑点的链表，您就可以使用普通的链表替代 \text{set}，复杂度 O(n^2+nmk^2)。
• 一些实现细节留待下面讨论。

细节

• 链表如何表示贡献？
• 具体地讲，定义一段链左端点的左边空白和右端点右边空白所代表的区间内的段为这段链的贡献，这些贡献包含在内部恰好为 k 个点的段内，可以暴力统计贡献。
• 代码，这个数据下理论上比分治要优。