Количество инверсий

Количество инверсий

Пусть у нас есть некоторая перестановка $a$. Инверсией называется пара индексов $i$ и $j$ такая, что $i < j$ и $a[i] > a[j]$. > Найти количество инверсий в данной перестановке.

Наивный алгоритм

Эта задача легко решается обычным перебором двух индексов за $O(n^2)$:

Реализация

 1 int a[n], ans = 0;
 2 
 3 for (int i = 0; i < n; ++i) {
 4     for (int j = i + 1; j < n; ++j) {
 5         if (a[i] > a[j]) {
 6             ans++;
 7         }
 8     }
 9 }
10 
11 cout << ans << endl;

Алгоритм за $O(n\log(n))$

Внезапно эту задачу можно решить используя сортировку слиянием, слегка модифицируя её. Оставим ту же идею. Пусть мы умеем находить количество инверсий в массиве размера $n$, научимся находить количество инверсий в массиве размера $2n$.

Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?

Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.

Рассмотрим число $A$ в левой половине. В скольких инверсиях между половинами оно участвует? В количестве, равному количеству чисел в правой половине меньше, чем оно. Знаем ли мы это количество? Да! Ровно в тот момент, когда мы число $A$ вносим в слитый массив, второй указатель указывает на первое число в правой половине, которое больше чем $A$.

Значит в тот момент, когда мы добавляем число $A$ из левой половины, к ответу достаточно прибавить индекс второго указателя (минус начало правой половины). Так мы учтем все инверсии между половинами.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin