Подсчет инверсий в изменяющемся массиве

Question

У вас есть массив A[] размера (1 ≤ N ≤ 10 ^ 5). Для каждого из 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

Я знаю, как найти число инверсии в массиве через MergeSort в O (NlogN). Однако, если бы я должен был явно сгенерировать каждый массив для каждого значения i, это был бы алгоритм O (N ^ 2logN), который не проходил бы во времени.

Одним из наблюдений, которое я сделал, было то, что инверсии увеличиваются с увеличением i. Это имеет смысл, потому что, когда все записи 0, инверсий не будет (так как они отсортированы), но по мере увеличения максимального значения записи, запись может стать больше, чем записи, которые ранее имели одинаковое значение.

Таким образом, вы можете начать с A[] только с 0 и продолжать увеличивать i. Вы можете использовать свой ответ для предыдущих значений i, чтобы определить ответ для больших значений i. Тем не менее, если вы сканируете каждый массив, вы все равно получите алгоритм O (N ^ 2).

Как я могу решить эту проблему?

Answer 1

Я сделаю удар. Мы будем рассматривать запросы в порядке убывания, поэтому от i = N-1, ... до 0. Прежде всего, обратите внимание, что когда мы сжимаем все A [j]> i в i, любой A [j] = я больше не буду вызывать инверсию с элементами больше, чем у него с меньшим индексом.

Например, скажем, у нас есть A = [1, 2, 5, 4] и мы уменьшаем A [2] до 4. Тогда у нас есть A = [1, 2, 4, 4] и наш единственный инверсия исчезает. Таким образом, для каждого j мы можем посчитать количество элементов в A с меньшим индексом и большим значением, и обозначить это V [j], «количество инверсий, которые оно вносит». Мы находим общее число инверсий в исходном массиве, а затем для каждого i = N-1, ..., 0 мы удаляем V [j] из общего числа инверсий для всех 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)

И мы получаем желаемые результаты. Детали реализации могут отличаться; Вы можете найти число элементов больше, чем A [j] с меньшим индексом, используя Fenwick Tree или что-то подобное. Этот алгоритм выполняется за время O (NlogN).