计算不断变化的数组中的反转
Counting inversions in a changing array
您有一个大小为 A[] 的数组 (1 ≤ N ≤ 10^5)。对于每个 i = 0, 1, 2, ..., N - 1，如果所有大于 i 的条目都减少到 i，我们想要确定数组中的反转次数。
An inversion is defined as two entries A[i] and A[j] where A[i] > A[j] and i < 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 找到数组中的反转次数。但是，如果我要为 i 的每个值显式生成每个数组，这将是一个不会及时传递的 O(N^2logN) 算法。
我的一个观察是，随着 i 的增加，倒置也在增加。这是有道理的，因为当所有条目都是 0 时，不会发生倒置（因为它已排序），但是随着您不断增加最大条目值，该条目可能会变得比以前具有相同值的条目更大.
所以你可以从只有 0 的 A[] 开始，然后继续增加 i。您可以使用您对 i 的先前值的答案来确定 i 的较大值的答案。尽管如此，如果您扫描每个数组，您仍然会得到一个 O(N^2) 算法。
我该如何解决这个问题？
我会尝试一下。我们将按降序考虑查询，因此从 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]，即"number of inversions it contributes"。我们找到原始数组中的反转总数，然后对于每个 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)。
您有一个大小为 A[] 的数组 (1 ≤ N ≤ 10^5)。对于每个 i = 0, 1, 2, ..., N - 1，如果所有大于 i 的条目都减少到 i，我们想要确定数组中的反转次数。
An inversion is defined as two entries
A[i]andA[j]whereA[i] > A[j]and i < 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 找到数组中的反转次数。但是，如果我要为 i 的每个值显式生成每个数组，这将是一个不会及时传递的 O(N^2logN) 算法。
我的一个观察是，随着 i 的增加，倒置也在增加。这是有道理的，因为当所有条目都是 0 时，不会发生倒置（因为它已排序），但是随着您不断增加最大条目值，该条目可能会变得比以前具有相同值的条目更大.
所以你可以从只有 0 的 A[] 开始，然后继续增加 i。您可以使用您对 i 的先前值的答案来确定 i 的较大值的答案。尽管如此，如果您扫描每个数组，您仍然会得到一个 O(N^2) 算法。
我该如何解决这个问题？
我会尝试一下。我们将按降序考虑查询，因此从 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]，即"number of inversions it contributes"。我们找到原始数组中的反转总数，然后对于每个 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)。