С помощью каких алгоритмов, кроме сортировки слиянием, можно найти количество инверсий в массиве?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | ecnerwala | 3654 |
3 | jiangly | 3627 |
4 | jqdai0815 | 3620 |
5 | orzdevinwang | 3612 |
6 | Benq | 3586 |
7 | Radewoosh | 3582 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3474 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | atcoder_official | 153 |
5 | maroonrk | 152 |
6 | -is-this-fft- | 148 |
6 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 145 |
10 | cry | 144 |
С помощью каких алгоритмов, кроме сортировки слиянием, можно найти количество инверсий в массиве?
Название |
---|
С помощью любой структуры данных, которая умеет делать обновление в точке и считать сумму на отрезке. Например, с помощью Дерева Отрезков или Дерева Фенвика. Изначально в структуре нули. Будем идти по нашему массиву v и прибавлять в точке v[i] единицу. Теперь, когда стоим в i, прибавим к кол-ву инверсий sum(v[i] + 1, INF). Это верно, так как мы по факту учитываем все числа, которые больше нашего, но встретились нам раньше. Тогда асимптотика будет O(NlogN).
Можно идти с конца и поддерживать какой-нибудь массив
P
. Пусть мы сейчас находимся на каком-нибудь элементеA[i]
нашего массива. Тогда мы в массивеP
на позицииA[i]
прибавим единицу (то есть, скажем, что такое число встретилось у нас на суффиксе). Тогда чему равно кол-во инверсий для текущего элемента в массивеA[i]
? Правильно — сумма всех чисел в массивеP
на всех индексах, начиная с1
и заканчиваяA[i]-1
. Для операции обновления суммы можно использовать ДО. И да, если числа в массиве большие, то можно сначала сжать их. От этого наш ответ не поменяется.Без объяснений, просто моя реализация с использованием Дерева Фенвика вместо Дерева Отрезков. + Делаю сжатие координат, т.е. превращаю массив из -1, -7, 0, 4, -1 в 1, 0, 2, 3, 1чтобы работало на $$$a_i \in [-10^9; +10^9]$$$