algorithm - 计算左下象限的点数？

Question

我无法理解 solution到算法 problem

特别是，我不明白这部分代码是如何或为什么

s += a[i];
total += query(s);
update(s);

允许您计算每个点的左下象限中的点总数。

有人可以详细说明吗？

Answer 1

作为平面问题的类比，请考虑以下问题:

1. 对于位于 (x, y) 左下象限的点 (a, b)，a < x & b < y;因此，形式为 (i, P[i]) 的点位于左下象限 的 (j, P[j]) 当且仅当 i < j 且 P[i] < P[j]
2. 当按升序迭代时，所有较早考虑的点都位于与当前 (i, P[i]) 相比的左侧
3. 所以只需要找到所有小于 P[i] 的 P[j] 就可以了

*当前点指的是你引用的for循环的当前迭代中考虑的点，即(i, P[i])

让我们定义另一个数组，C[s]:

C[s] = Number of Prefix Sums of array A[1..(i - 1)] that amount to s

所以#3 的解变成了总和 ... C[-2] + C[-1] + C[0] + C[1] + C[2] ... C[P[i] - 1],即C[P[i]]的前缀和

用BIT存储C的前缀和，定义query(s)为:

query(s) = Number of Prefix Sums of array A[1..(i - 1)] that amount to a value < s

使用这些定义，给定代码中的 s 为您提供当前索引 i (P[i]) 的前缀总和。 total 构建答案，update 只是将 P[i] 添加到 BIT。

我们必须对所有 i 重复此方法，因此需要 for 循环。

PS:它使用一种称为二叉索引树 (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees) 的数据结构进行操作。如果您不熟悉它，我建议您查看链接。

编辑: 给定一个数组 S 和一个值 X。您可以将 S 拆分为两个不相交的子数组，使得 L 具有 S 中小于 X 的所有元素，而 H 具有大于或等于 X 的元素。

A: All elements of L are less than all elements of H.

S 的任何子序列 T 都有 L 的一些元素和 H 的一些元素。假设它有 L 的 p 个元素和 H 的 q 个元素。当 T 被排序为 T' 时，L 的所有 p 个元素出现在由于 A 的 H 的 q 个元素。

Median being the central value is the value at location m = (p + q)/2

直觉上认为 q >= p 意味着中位数位于 X 中，作为证明: T'中[1..p]位置的值属于L。因此对于H中的中位数，它的位置m应该大于p:

m > p
(p + q)/2 > p
p + q > 2p
q > p
B: q - p > 0

对于计算机 q - p，我将 T' 中所有属于 L ( < X ) 的元素替换为 -1，如果它们属于 H ( >= X)，则替换为 +1 T 看起来像 {-1, -1, -1... 1, 1, 1} 它有 p 次 -1 和 q 次 1。T' 的总和现在会给我:

Sum = p * (-1) + q * (1)
C: Sum = q - p

我可以使用这些信息来找到 B 中的值。

所有子序列的形式都是 {A[i], A[i + 2], A[i + 3] ... A[j + 1]} 因为它们是连续的，计算 A[i 的总和] 到 A[j + 1]，我可以用 P[i] = A[1] + A[2] + .. A[i - 1] 计算 A[i] 的前缀和 从 A[i] 到 A[j] 的子序列之和可以计算为 P[j] - P[i](j 大于 j 和 i) 考虑到 C 和 B，我们得出结论:

Sum = P[j] - P[i] = q - p  (q - p > 0)
P[j] - P[i] > 0
P[j] > P[i]

j > i 和 P[j] > P[i] 给你一个中位数 >= X 的每个解决方案

总结:

1. 如果 A[i] 小于 X，则将所有 A[i] 替换为 -1，否则替换为 -1
2. A[i]的计算机前缀和
3. 对于每一对 (i, P[i])，计算位于其左下象限的对。