计数变化数组中的求反数

Question

您有一个大小为（1≤N≤10 ^ 5）的数组A[]。对于i = 0, 1, 2, ..., N - 1中的每一个，如果所有大于i的条目都减少到i，我们想确定数组中的求反数。

反转定义为两个条目A[i]和A[j]，其中A[i] > A[j]和i

示例：

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）算法。

我该如何解决这个问题？

您的数组A []的大小为（1≤N≤10 ^ 5）。对于i = 0、1、2，...，N-1中的每一个，如果所有大于i的项都减少到i，我们想确定数组中的求反数。一个...

Answer 1

我将对此采取行动。我们将按降序考虑查询，因此从i = N-1，...下降到0。首先，请注意，当我们将所有A [j