谁能帮我完成这个任务 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)
。由于数组中的数字与
1
和 n
不同,因此您的 BIT 数组的大小为 n
并且复杂性在 n
中是对数的。如果您想了解如何解决初始问题的详细信息,请编写,尽管它很经典,您应该可以轻松地在 Google 上找到代码。
注意: 这个问题也有一个使用 merge sort 的漂亮解决方案,你可能想考虑一下。
关于c++ - SPOJ INVCNT - 如何?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/17385037/