提问人： 提问时间：3/28/2020 更新时间：3/28/2020 访问量：316
对变化数组中的倒置进行计数
Counting inversions in a changing array
问：
你有一个大小为 （1 ≤ N ≤ 10^5） 的数组。对于每个 ，如果所有大于 的条目都减少到 ，我们想要确定数组中的反转次数。A[]i = 0, 1, 2, ..., N - 1ii
反转定义为两个条目，其中 和 i < j。
A[i]A[j]A[i] > A[j]
例：
A[] = {3， 2， 1， 5， 2， 0， 5}
i = 0: {0, 0, 0, 0, 0, 0, 0} Inversions: 0
i = 1: {1, 1, 1, 1, 1, 0, 1} Inversions: 5
i = 2: {2, 2, 1, 2, 2, 0, 2} Inversions: 7
i = 3: {3, 2, 1, 3, 2, 0, 3} Inversions: 10
i = 4: {3, 2, 1, 4, 2, 0, 4} Inversions: 10
i = 5: {3, 2, 1, 5, 2, 0, 5} Inversions: 10
i = 6: {3, 2, 1, 5, 2, 0, 5} Inversions: 10
因此，您的输出将是：
0
5
7
10
10
10
10
我知道如何通过 O（NlogN） 中的 MergeSort 查找数组中的反转次数。但是，如果我要显式地为 的每个值生成每个数组，它将是一个不会及时传递的 O（N^2logN） 算法。i
我观察到的一个结果是，反转随着增加而增加。这是有道理的，因为当所有条目都是 时，不会有反转（因为它是排序的），但是随着您不断增加最大条目值，该条目可能会变得比以前具有相同值的条目更大。i0
因此，您可以从只有 0 的 an 开始，然后继续增加。您可以使用先前值的答案来确定较大值 的答案。不过，如果你扫描每个数组，你仍然会得到一个 O（N^2） 算法。A[]iii
我该如何解决这个问题？
答：
1赞
aeternalis1
3/28/2020
#1
我会尝试一下。我们将按降序考虑查询，因此从 i = N-1， ...，向下到 0。首先，请注意，当我们将所有 A[j] > i 缩小到 i 时，任何 A[j] = i 将不再导致元素大于索引较小元素的反转。
例如，假设我们有 A = [1， 2， 5， 4]，我们将 A[2] 缩小到 4。然后我们有 A = [1， 2， 4， 4]，我们的单反演消失了。因此，对于每个 j，我们可以计算 A 中索引较小且值较大的元素数量，并表示这个 V[j]，即“它贡献的反转次数”。我们找到原始数组中的反转总数，然后对于每个 i = N-1,...,0，我们从所有 j 的反转总数中删除 V[j]，使得 V[j] = i。
让我们将其应用于给定的示例。
A = [3, 2, 1, 5, 2, 0, 5]
V = [0, 1, 2, 0, 2, 5, 0]
然后，通过 i = 6， 5， 4， 3， 2， 1：
i = 6: A = [3, 2, 1, 5, 2, 0, 5], res = 10 (original calculation using merge sort)
i = 5: A = [3, 2, 1, 5, 2, 0, 5], res = 10 (subtract nothing because V[3] = V[6] = 0)
i = 4: A = [3, 2, 1, 4, 2, 0, 4], res = 10 (subtract nothing because no occurrences of 4)
i = 3: A = [3, 2, 1, 3, 2, 0, 3], res = 10 (10 - V[0] = 10)
i = 2: A = [2, 2, 1, 2, 2, 0, 2], res = 7 (10 - V[1] - V[4] = 10 - 1 - 2 = 7)
i = 1: A = [1, 1, 1, 1, 1, 0, 1], res = 5 (7 - V[2] = 7 - 2 = 5)
i = 0: A = [0, 0, 0, 0, 0, 0, 0], res = 0 (5 - V[5] = 5 - 5 = 0)
我们得到了我们想要的输出。实现细节可能有所不同;您可以使用 Fenwick Tree 或类似方法找到指数低于 A[j] 的元素数量。该算法在 O（NlogN） 时间内运行。
评论