计算矩形的数量
Count number of rectangles
存在 NxM 网格，编号为 1,2,...NM（按行进行编号。第一行将包含来自 1[=48 的数字=] 到 M，第二行将包含 M+1 到 2M 等等）。 =13=]
还有X个数字的列表，范围从1到NM。
问题：*计算边长在网格线上的矩形总数，它恰好包含列表中的 K 个点 [=每个 K 的 27=]X
范围从 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
他是O(n^2 * m^2)的方法。
行网格线编号为row[0], ..., row[n]，列网格线编号为column[0], ..., column[n]。令 f[x][y] 表示包含在顶边 - row[0]、底边 - row[x]、左边 - column[0]、右边的矩形中 X 中的点数边 - column[y]。请注意，您只能在 O(n*m) 时间内以自下而上的方法计算 f（这是动态规划）。
现在每个矩形的顶边 - 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)。
存在 NxM 网格，编号为 还有X个数字的列表，范围从1到NM。 问题：*计算边长在网格线上的矩形总数，它恰好包含列表中的 K 个点 [=每个 K 的 27=]X1,2,...NM（按行进行编号。第一行将包含来自 1[=48 的数字=] 到 M，第二行将包含 M+1 到 2M 等等）。 =13=]
示例超过 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
他是O(n^2 * m^2)的方法。
行网格线编号为row[0], ..., row[n]，列网格线编号为column[0], ..., column[n]。令 f[x][y] 表示包含在顶边 - row[0]、底边 - row[x]、左边 - column[0]、右边的矩形中 X 中的点数边 - column[y]。请注意，您只能在 O(n*m) 时间内以自下而上的方法计算 f（这是动态规划）。
现在每个矩形的顶边 - 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)。