c++ - SPOJ INVCNT - 怎么样？

Question

谁能帮我完成这项任务http://www.spoj.com/problems/INVCNT/。首先，我尝试以 BIT 方式思考，但我做不到。谁能用 BIT 解释一下这个任务的解决方案。BIT-二进制索引树c ++

score 6 · Accepted Answer

假设您知道如何O(log n)使用 BIT 在每个查询和更新中解决以下问题：

Given an array A[1 .. n], implement the following functions efficiently:
query(x, y) = return A[x] + A[x+1] + ... + A[y]
update(x, v) = set A[x] = v

您可以像这样解决当前的问题：首先，标准化您的数组值。这意味着您必须转换所有值，使它们位于区间内[1, n]。你可以用排序来做到这一点。例如，5, 2, 8将成为2, 1, 3. （注：1、2、3为按5、2、8排序的索引）

然后，对于每个，我们将回答使用 elements 生成i了多少反转。为此，我们需要找到之前大于的元素个数。这相当于.A[i]j < iiiquery(A[i] + 1, n)

在此查询之后，我们执行update(A[i], 1).

以下是它的工作原理：我们的 BIT 数组最初将用零填充。此数组中的位置k为 1 表示我们k在迭代给定数组时遇到了该值。通过调用query(A[i] + 1, n)，我们可以找到之前的元素产生了多少反转A[i]，因为我们查询到目前为止我们已经迭代了多少比它大的元素。

找到这个后，我们需要标记A[i]为已访问。我们通过更新A[i]BIT 数组中的位置并在其上放置 1 来做到这一点update(A[i], 1)：

由于数组中的数字与1to不同n，因此您的 BIT 数组具有大小n且复杂度为 in 的对数n。

如果您想详细了解如何解决最初的问题，请写下，尽管它是经典的，您应该能够轻松地在 Google 上找到代码。

注意：这个问题也有一个你可能想要考虑的使用合并排序的漂亮解决方案。

1 回答 1