Prefix-Sum of Prefix-Sum of Ones

给定两个给定数组 A 和 B ，从这两个数组各取一个元素可以组成一个坐标 (x, y) 。现以这种方式获得两个坐标 P1 (x1, y1) 和 P2 (x2, y2) ，求有多少种取法，使得 x2 <= x1 ，y2 <= y1 。

Solution

如果我们分别将两个数组从小到大排序，并分别以 i 和 j 来索引两个数组，那么假设我们选定了 i 和 j 索引到的元素组成坐标，很显然同样使用 i ，j 索引的元素组成的坐标满足条件。同时我们知道，i - 1 和 j - 1 索引到的元素一定比 i 和 j 索引的元素小，所以我们可以这样计算对于 i 和 j 满足条件的数量：

-- f 计算对于 i j 满足条件的值

-- 很显然，i j 本身一定满足条件
f 0 0 = 1

-- 对于边界，我们只能累加它的左边或者下面
f i 0 = 1 + (f (i - 1) 0)
f 0 j = 1 + (f 0 (j - 1))

-- 注意，这里需要减去重复计算的部分
f i j = 1 + (f (i - 1) j) + (f i (j - 1)) - (f (i - 1) (j - 1))

注意到这其实是一个二维前缀和，每一个位置的元素都是 1 。现在我们对这些式子进行化简。

-- 第一个式子不需要化简
f' 0 0 = 1

-- 对于边界，实际上就是累加 1
f' i 0 = i + 1
f' 0 j = j + 1

-- 这里需要一些技巧
f' i j = 1 + (f (i - 1) j) + (f i (j - 1)) - (f (i - 1) (j - 1))
-- 注意到 i j 处的前缀和实际上是上一行的前缀和，加上这一行的和
-- 本行的和为 i + 1
= (i + 1) + (f' (i - 1) j)
-- 在 j 不变的情况下，每一行的和实际上都是 i + 1
= (i + 1) * (j + 1)

化简得到的结果为 f i j = (i + 1) * (j + 1) ，对于边界情况同样满足。接下来我们需要进行下一步：计算对于 i j ，求所有 i' <= i , j' <= j 的所有满足条件的值之和。首先我们给出前缀和的一般形式：

-- func 是计算 i j 处的值的函数
presum 0 0 func = func 0 0
presum i 0 func = (func i 0) + (presum (i - 1) 0)
presum 0 j func = (func 0 j) + (presum 0 (j - 1))
presum i j func = (func i j) + (presum (i - 1) j) + (presum i (j - 1)) - (presum (i - 1) (j - 1))

假设 g 为求取这个值的函数。我们对一般形式进行替换：

g 0 0 = f 0 0
g i 0 = (f i 0) + (g (i - 1) 0)
g 0 j = (f 0 j) + (g 0 (j - 1))
g i j = (f i j) + (g (i - 1) j) + (g i (j - 1)) - (g (i - 1) (j - 1))

现在把 f 的值代入进去：

g 0 0 = 1
g i 0 = i + 1 + (g (i - 1) 0)
g 0 j = j + 1 + (g 0 (j - 1))
g i j = (i + 1) * (j + 1) + (g (i - 1) j) + (g i (j - 1)) - (g (i - 1) (j - 1))

边界的两种情况是很容易化简的：

-- 应用等差数列求和公式
g i 0 = (i + 2) * (i + 1) / 2
g 0 j = (j + 2) * (j + 1) / 2

最后一种情况我们应用之前使用的技巧：

-- 注意到 i j 处的前缀和实际上是上一行的前缀和，加上这一行的和
-- 本行的和就是 (g 0 j) * (i + 1)
g i j = ((j + 2) * (j + 1) / 2) * (i + 1) + (g (i - 1) j)
-- 在 j 不变的情况下，每一行的和都是 (g 0 j) * i
= ((i + 2) * (i + 1) / 2) * ((j + 2) * (j + 1) / 2)
= (i + 2) * (i + 1) * (j + 2) * (j + 1) / 4

所以，我们只需要知道两个数组的长度，就能计算出满足条件的个数：

prefix_sum_of_prefix_sum_of_ones m n = (m + 1) * m * (n + 1) * n / 4