Расскажите пожалуйста идею алгоритма. Не сомневаюсь, что задача довольно проста, но я ведь
еще только учусь...
P.S Разумеется алгоритм должен работать не за O(N * N), а за O(N * logN).

IL3, какого алгоритма? каких инверсий?

Пусть задана последовательность целых чисел a[1],a[2],...,a[n], все числа в ней различны и находятся в промежутке [1..n]. Инверсия - это такая последовательность индексов 0 < i < j < n + 1, что a[i] > a[j].
А алгоритм должен искать эти самые инверсии в массиве.

модифицируй сортировку слиянием

Создаем массив из элементов вида

Далее сортируем массив по zn слиянием. Потом уже ищем инверсии в получившемся массиве по position. Т.е. берем первый элемент и от него двигаемся далее пока выполяняется условие инверсии. Как только перестает выполняться переходим ко второму элементу и так далее.

Количество инверисий квадратично.


Интересно как вы найдете их все быстрей чем за квадратичную сложность.


опыт подсказывает, что это невозможно.

А! точно! Мы это в конце первого семестра по Линейке прошли...
Слушай, esperant0. А можно посчитать сложность моего алгоритма? Я в сложностях не силен 

Сортировка слиянием nlgn

А дальше когда идет поиск инверсий, в худшем случае, когда массив упорядочен в обратном порядке, понадобиться (n^2)/2 сравнений

esperant0, 
>А дальше когда идет поиск инверсий
инверсии нужно искать не после, а во время сортировки слиянием.  Если мы обнаруживаем в старшем сливаемом сегменте меньшее число, чем в младшем, то сразу не на единицу число инверсий увеличиваем, а  на длину дистанции, за счет этого и достигается асимптотика нужная

Еще раз.

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

Каким образом вы обеспечите ассимптотику nlgn?

SoWa дал правильный алгоритм, только сам в нем запутался:

• Двумеризуем массив, т.е. a[i] -> a[a[i],i]
• Выполняем сортировку по первому индексу (читай - исходному массиву). O(N*logN).
• Далее в один проход получаем все пары. А вот тут никуда не деться, O(N*N). Вернее так: это не количество сравнений, которое O(N), это количество записей в выходной поток пар инверсии будет O(N*N).

Т.е. O(N*N) получаем не на стадии просчета (там честные O(N*logN)), а на стадии вывода результата.



Какое может быть "перестает выполняться"? массив ОТСОРТИРОВАН!


Когда "массив упорядочен в обратном порядке", следует поправить код, сменив сортировку по возрастанию на сортировку по убыванию (или наоборот).

esperant0, 
Я понял задачу как подсчет количества инверсий, а не вывод инверсионных пар.

Еще есть простой алгоритм кроме сортировки слиянием...
С помощью дерева отрезков..
Вначале проходим по массиву и добавляем все числа в дерево...
Потом за второй проход подсчитываем и удаляем текущий элемент из дерева...
Дерево отрезков позволяет узнать количество элементов меньших а[i] в дереве...
Это работает за NLogN если не надо выводить элементы...А выводить - это маразм...
Тогда никакой эффективности не надо..