SPOJ INVCNT - 怎么样？

Question

任何人都可以帮我完成这项任务http://www.spoj.com/problems/INVCNT/.首先,我尝试用BIT方式思考,但我不能.任何人都可以用BIT解释这个任务的解决方案.BIT-二进制索引树c ++

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).

由于数组中的数字与1to 不同n,因此您的BIT数组具有大小n,并且复杂性是对数的n.

如果您想了解如何解决最初问题的详细信息,请写一下,虽然它是经典的,但您应该能够在Google上轻松找到代码.

注意:问题也有一个使用合并排序的漂亮解决方案,您可能需要考虑.