algorithm - 计算矩形的数量

Question

存在 NxM 网格，编号为 1,2,...NM(编号按行进行。第一行将包含来自 1 的数字 到 M，第二行将包含 M+1 到 2M 等等)。

还有 X 个数字的列表，范围从 1 到 NM。

问题:*计算边长在网格线上的矩形总数，它恰好包含列表 X 中的每个点 K K 的范围从 0 到 X 的长度。

示例值超过 1000 字:

Let N=2, M=2 and X=[1,2].
Rectangle containing 0 points: 3
Rectangle containing 1 points: 4
Rectangle containing 2 points: 2

我的方法

我知道这个网格可能的矩形总数是n(n+1)m(m+1)/4，但想不出别的。

编辑
1 ≤ N, M ≤ 10^7
1 ≤ X 的长度 ≤ 10^5
1 ≤ 列表中的元素 X ≤ N*M

Answer 1

他是一个O(n^2 * m^2)方法。

将行网格线编号为row[0], ..., row[n]列网格线为 column[0], ..., column[n] .让f[x][y]表示 X 中的点数包含在顶边的矩形中 - row[0] , 底部 - row[x] , 左侧 - column[0] , 右侧 - column[y] .请注意，您可以计算 f自下而上的方法仅适用于 O(n*m)时间(这是动态规划)。

现在对于每个带有顶边的矩形 - row[x1] , 底部 - row[x2] , 左侧 - column[y1] , 左边 column[y2] ( x1<x2 , y1<y2 ) 你可以计算出 X 的总数指向它是f[x2][y2]-f[x1][y2]-f[x2][y1]+f[x1][y1] .在你计算出你放入计数图中的数字后，它与 X 中的点数相关联。包含在当前矩形中以及您遇到此数字的次数。您可以使用 hashmap .

总共有 O(n^2*m^2) .

在您的示例中，对于 f你有:

f[0][0] = f[0][1] = f[0][2] = f[1][0] = f[2][0] = 0
f[1][1] = 1
f[1][2] = 2
f[2][1] = 1
f[2][2] = 2

现在，对于矩形 row[0], row[1], column[1], column[2]你有 X 中的点数包含在这个矩形中的是:

number = f[1][2]-f[0][2]-f[1][1]+f[0][0] = 2-0-1+0 = 1

这是正确的。

请注意，暴力破解方法很复杂 O(n^4 * m^4) .