Алгоритм с O (nlg n) Время выполнения

Question

a1, a2, ..., an порядковые номера приведены. Теперь, дать алгоритм с O(nlg n) времени выполнения для расчета количества пара (i, j) для i < j и ai > aj.

Ввод: В число первых экземпляров входит первое. По каждому номеру теста пришло n номер для первого, а затем a1, a2, ..., an в следующей строке. N <= 100000

ai <= 100000000 

Теперь я хочу, выход следующим образом:

Выход: Для каждого теста печатается только один номер (то есть значение спросил в начале этого вопроса).

Пример ввода:

2 
4 
3 2 1 5 
5 

8 9 3 2 1 

Образец Выход:

3 

9 

Answer 1

Это стандартная проблема алгоритм известен как "подсчета" Inversion. Я просто дам вам основной источник, а не объясню с нуля. Проверьте это link. Ключи:

i) Вы просто разделите массив на 2 равные части.

ii) Затем получите ответ для обеих частей.

iii) При слиянии просто нужно учитывать, как цифры в левом сегменте меньше, чем правый сегмент. Вот что добавило наконец ответ.

iv) верните его.

Все. Вы должны выполнить все операции, которые вы делаете в сортировке слияния. Наряду с этим вам просто нужно правильно определить количество инверсий во время операции слияния.