c++ - SPOJ INVCNT - 怎么样？

Question

谁能帮我完成这个任务http://www.spoj.com/problems/INVCNT/ .首先，我尝试以 BIT 方式思考，但我做不到。任何人都可以用 BIT 解释这个任务的解决方案。 BIT- 二叉索引树语言

Answer 1

假设您知道如何解决 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排序的索引)

然后，对于每个 i ，我们将回答多少次反转A[i]生成元素 j < i .为此，我们需要找到 i 之前的元素数。大于 i .这相当于 query(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) .

因为数组中的数字不同于 1至 n ，您的 BIT 数组的大小为 n并且复杂度在 n 中呈对数关系.

如果您需要有关如何解决初始问题的详细信息，请写下来，尽管它是经典的并且您应该能够轻松地在 Google 上找到代码。

注意:这个问题还有一个很好的解决方案，使用merge sort你可能想考虑一下。