algorithm - 绘制网格的 3x3 子矩形

Question

最近参加了一个编码比赛，想不通this question.问题陈述如下

You have a 10^9 * 10^9 grid of white cells with 10^5 of them painted black. For each integer j from 0 to 9, output the number of 3x3 subrectangles that contain exactly j black cells. The time limit is 3 seconds and the memory limit is 256mb.

我有一个模糊的想法，大致如下:遍历黑色单元格并检查以黑色单元格为中心的 5x5 矩形中的单元格，然后计算 3x3 矩形(我认为这将是一个 O(n ) 解决方案，其中 n 是黑色单元格的数量，但我不确定如何实现这个或如何处理重复计数。

该网站有一个关于这个问题的社论，但它是日语的，谷歌翻译也没有用。

Answer 1

我的算法如下:

有 2 个有序集，1 用于点，1 用于每个 3x3 子矩形的左上角坐标。这是为了有效地搜索重复项和黑色单元格

1. 对于每个黑色单元格，处理它所在的 9 个 3x3 矩形

2. 对于每个 3x3 矩形，检查左上角坐标是否已经在集合中

   2a。如果是，忽略矩形

   2b。如果不是，则计算矩形中黑色单元格的数量(通过检查每个单元格中是否存在黑色单元格)

3. 将新的左上角坐标插入集合中，并将 1 添加到适当的计数器。

要计算没有任何黑色单元格的 3x3 矩形的数量，您可以采用 (H-2)*(W-2) - 至少有 1 个的矩形的数量黑色单元格

该算法应该采取 ~O(Nlog(N)) 步骤。第 1 步花费 O(N) 时间，第 2 步花费 O(9*9*logN) = O(logN)。第 3 步花费 O(logN) 时间。