1

我无法理解算法问题的解决方案

特别是，我不明白这部分代码的方式或原因

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

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

有人可以详细说明吗？

4

1 回答 1

1

作为平面问题的类比，考虑一下：

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

*当前点是指您引用的 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) = 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 个元素出现在 的 q 个元素之前H 因为 A。

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]，我可以计算 A[i] 的前缀和，其中 P[i] = A[1] + A[2] + .. A[i - 1] 从 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])，计算位于其左下象限的对。
于 2014-05-17T17:00:55.890 回答