谁能帮我完成这个任务 http://www.spoj.com/problems/INVCNT/ 。首先,我尝试以 BIT 的方式思考,但我不能。谁能用 BIT 解释这个任务的解决方案。 BIT- 二叉索引树
C++

最佳答案

假设您知道如何在每个查询中解决 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] 标记为已访问。我们通过更新 BIT 数组中的位置 A[i] 并在其上放置 1 来完成此操作: update(A[i], 1)

由于数组中的数字与 1n 不同,因此您的 BIT 数组的大小为 n 并且复杂性在 n 中是对数的。

如果您想了解如何解决初始问题的详细信息,请编写,尽管它很经典,您应该可以轻松地在 Google 上找到代码。

注意: 这个问题也有一个使用 merge sort 的漂亮解决方案,你可能想考虑一下。

关于c++ - SPOJ INVCNT - 如何?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/17385037/

10-11 23:06
查看更多