绘画网格的3x3子矩形
最近我参加了一场编码竞赛，无法弄清楚这个问题。 问题陈述如下
你有一个10^9 * 10^9格子的白色细胞，其中10^5涂成黑色。 对于每个整数j从0到9 ，输出包含恰好3×3 subrectangles数量j黑细胞。 时间限制为3秒，内存限制为256mb。
我有一个模糊的想法，如下所示：遍历黑色单元格并检查以黑色单元格为中心的5x5矩形中的单元格，然后计算3x3矩形（我相信这将是一个O(n)解决方案，其中n是黑细胞的数量，但我不知道如何去执行这个或如何处理重复计算。
该网站有一个编辑这个问题，但它是在日本和谷歌翻译是没有用的。
我的算法如下：
有2个有序集合， 1用于点，1个用于每个3x3矩形的左上角坐标。 这是为了有效地搜索重复和黑色单元格
对于每个黑色单元格，处理它所在的9个3x3矩形
对于每个3x3矩形，检查左上角坐标是否已经在该集合中
2A。 如果是，请忽略该矩形
2B。 如果不是，则计算矩形中黑色单元的数量（通过检查每个单元中是否存在黑色单元）
将新的左上角坐标插入到集合中，并将1加到适当的计数器中。
要计算没有黑色单元格的3x3矩形的数量，可以取(H-2)*(W-2) - number of rectangles with at least 1 black cell
该算法应该采取~O(Nlog(N))步骤。 步骤1取O(N)时间，步骤2取O(9*9*logN) = O(logN) 。 第3步需要O(logN)时间。