Задача

Дан массив, посчитать количество инверсий. Инверсия - это пара индексов $i$, $j$ таких, что: $i$ < $j$, а также $array[i]$ > $array[j]$. Нам нужно посчитать все такие пары в массиве.

Алгоритм решения

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

$количество\,инверсий + длина\,массива - текущий\,индекс\,элемента$

Все элементы массива, индекс которых больше текущего, будут меньше, чем наш элемент, так как массивы сортируются.

Вычислительная сложность

Временная сложность - $O(n * log_2 n)$

Псевдокод

Функция разделить_пополам(массив)    
    Если размер массива больше 1    
        середина = размер массива // 2    
        Вернуть [массив[:середина], массив[середина:]]    
    Вернуть массив    
    
Функция разделить_массив(массив)    
    Если размер массива равен 1    
        Вернуть [массив]    
            
    первая_половина, вторая_половина = разделить_пополам(массив)    
    Вернуть разделить_массив(первая_половина) + разделить_массив(вторая_половина)    
    
Функция сортировать_и_сливать(массивы)    
    первая_половина, вторая_половина = массивы    
    i = j = количество_инверсий = 0    
        
    новый_массив = пустой список    
    Пока i < размер первой_половины и j < размер второй_половины    
        Если первая_половина[i] < вторая_половина[j]    
            добавить первая_половина[i] в новый_массив    
            i += 1    
        Иначе    
            добавить вторая_половина[j] в новый_массив    
            количество_инверсий += (размер первой_половины - i)    
            j += 1    
        
    Если i < размер первой_половины или j < размер второй_половины    
        добавить оставшиеся элементы из первой_половины[i:размер первой_половины] в новый_массив    
        добавить оставшиеся элементы из второй_половины[j:размер второй_половины] в новый_массив    
            
    Вернуть новый_массив, количество_инверсий    
    
Функция слияние(массив, количество_инверсий = 0)    
    финальный_массив = пустой список    
        
    Если размер массива нечетный    
        добавить пустой список в массив    
            
    Для каждого i от 0 до (размер массива - 1) с шагом 2    
        текущий_массив, инверсии = сортировать_и_сливать([массив[i], массив[i + 1]])    
        количество_инверсий += инверсии    
        добавить текущий_массив в финальный_массив    
            
    Если размер финального_массива равен 1    
        Вернуть финальный_массив[0], количество_инверсий    
            
    Вернуть слияние(финальный_массив, количество_инверсий)    
    
Функция сортировка_слиянием(массив)    
    массив = разделить_массив(массив)    
    Вернуть слияние(массив)

Реализация на Python

Аннотация:    
array_in_half - функция делит массив на две равные половины    
array - исходный массив    
middle - индекс, определяющий середину массива    
split_array - функция рекурсивно делит массив на подмассивы длиной 1    
first - первая половина массива после разделения    
second - вторая половина массива после разделения    
sort_merge - функция объединяет два отсортированных массива в один и подсчитывает количество инверсий    
arrays - пара отсортированных подмассивов для слияния    
cnt_inv - счетчик инверсий    
new_array - отсортированный массив    
merge - функция объединяет все подмассивы в исходный массив и подсчитывает количество инверсий    
final_array - массив после сортировки и слияния всех подмассивов    
cnt - счетчик инверсий    
merge_sort - функция сортирует массив и подсчитывает количество инверсий методом сортировки слиянием  
  
def array_in_half(array):      
    if len(array) > 1:      
        middle = len(array) // 2      
        return [array[:middle], array[middle:]]     
             
    return array      
      
      
def split_array(array):      
    if len(array) == 1:      
        return [array]      
            
    first, second = array_in_half(array)      
    return split_array(first) + split_array(second)      
      
      
def sort_merge(arrays):      
    first, second = arrays      
    i = j = cnt_inv = 0      
        
    new_array = []      
    while i < len(first) and j < len(second):     
         
        if first[i] < second[j]:      
            new_array.append(first[i])      
            i += 1      
                
        else:      
            new_array.append(second[j])    
                
            cnt_inv += (len(first) - i)      
            j += 1      
                
    if i < len(first) or j < len(second):      
        new_array += first[i:len(first)]      
        new_array += second[j:len(second)]      
            
    return new_array, cnt_inv      
      
      
def merge(array, cnt=0):      
    final_array = []      
        
    if len(array) % 2 > 0:      
        array.append([])      
            
    for i in range(0, len(array)-1, 2):      
        curr, cnt_inv  = sort_merge([array[i], array[i + 1]])      
    
        cnt += cnt_inv       
        final_array.append(curr)      
            
    if len(final_array) == 1:      
        return final_array[0], cnt      
            
    return merge(final_array, cnt)      
      
      
def merge_sort(array):      
    array = split_array(array)      
    return merge(array)

Олимпиадная реализация на C++

Аннотация:    
typedef - переопределение имени типа данных    
split_array - функция рекурсивно делит массив на подмассивы длиной 1    
arr - исходный массив    
sing_arr - вектор векторов целых чисел, каждый из которых содержит один элемент из исходного массива    
sort_arrays - функция объединяет два отсортированных массива в один и подсчитывает количество инверсий    
arr1 - первая половина массива, которую нужно объединить и отсортировать    
arr2 - вторая половина массива, которую нужно объединить и отсортировать    
first - первая половина массива    
second - вторая половина массива    
cnt_inv - счетчик инверсий    
new_array - отсортированный массив    
merge - функция объединяет все подмассивы в исходный массив и подсчитывает количество инверсий    
cnt - счетчик инверсий    
final_array - массив после сортировки и слияния всех подмассивов    
merge_sort - функция сортирует массив и подсчитывает количество инверсий методом сортировки слиянием  
  
typedef vector<int> vi;    
typedef vector<vector<int>> vvi;    
    
vi split_array(vi &arr) {    
  vvi sing_arr;    
  for (int i : arr) {    
    sing_arr.push_back({i});    
  }    
    
  return sing_arr;    
}    
    
pair<vi, int> sort_arrays(vi &arr1, vi &arr2) {    
  vi first = arr1;    
  vi second = arr2;    
  int i = 0;    
  int j = 0;    
  int cnt_inv = 0;    
    
  vi new_arr;    
  while (i < first.size() and j < second.size()) {    
    if (first[i] < second[j]) {    
      new_arr.push_back(first[i]);    
      i++;    
    }    
    
    else {    
      new_arr.push_back(second[j]);    
      cnt_inv += (first.size() - i);    
      j++;    
    }    
  }    
    
  if (i < first.size() or j < second.size()) {    
    new_arr.insert(new_arr.end(), first.begin() + i, first.end());    
    new_arr.insert(new_arr.end(), second.begin() + j, second.end());    
  }    
    
  return make_pair(new_arr, cnt_inv);    
}    
    
pair<vi, int> merge(vvi &arr, int cnt) {    
  vvi final_arr;    
  if (arr.size() % 2 > 0) arr.push_back({});    
    
  for (int i = 0; i < arr.size() - 1; i += 2) {    
    pair<vi, int> res = sort_arrays(arr[i], arr[i + 1]);    
    cnt += res.second;    
    final_array.push_back(res.first);    
  }    
    
  if (final_arr.size() == 1) return final_arr[0];    
    
  return merge(final_arr, cnt);    
}    
    
pair<vi, int> merge_sort(vi &arr) {    
  vvi single_arr = split_array(arr);    
  return merge(single_arr, 0);    
}

Продуктовая реализация на C++

Аннотация:    
template - шаблон функции    
typename T - шаблонный тип данных параметра    
split_array - функция разделяет вектор на одноэлементные подмассивы    
array - исходный массив    
single_array - вектор векторов целых чисел, каждый из которых содержит один элемент из исходного массива    
sort_arrays - функция объединяет два отсортированных массива в один и подсчитывает количество инверсий    
array_1 - первая половина массива, которую нужно объединить и отсортировать    
array_2 - вторая половина массива, которую нужно объединить и отсортировать    
first - первая половина массива    
second - вторая половина массива    
cnt_inv - счетчик инверсий    
new_array - отсортированный массив    
merge - функция объединяет все подмассивы в исходный массив и подсчитывает количество инверсий    
cnt - счетчик инверсий    
final_array - массив после сортировки и слияния всех подмассивов    
merge_sort - функция сортирует массив и подсчитывает количество инверсий методом сортировки слиянием  
  
template <typename T>    
std::vector<std::vector<T>> split_array(std::vector<T>& array) {    
  std::vector<std::vector<T>> single_array;    
    
  for (T i : array) {    
    single_array.push_back({i});    
  }    
    
  return single_array;    
}    
    
std::pair<std::vector<T>, int> sort_arrays(std::vector<T>& array_1,    
                                           std::vector<T>& array_2) {    
  std::vector<T> first = array_1;    
  std::vector<T> second = array_2;    
  int i = 0;    
  int j = 0;    
  int cnt_inv = 0;    
    
  std::vector<T> new_array;    
  while (i < first.size() and j < second.size()) {    
    if (first[i] < second[j]) {    
      new_array.push_back(first[i]);    
      i++;    
    }    
    
    else {    
      new_array.push_back(second[j]);    
    
      cnt_inv += (first.size() - i);    
      j++;    
    }    
  }    
    
  if (i < first.size() or j < second.size()) {    
    new_array.insert(new_array.end(), first.begin() + i, first.end());    
    new_array.insert(new_array.end(), second.begin() + j, second.end());    
  }    
    
  return std::make_pair(new_array, cnt_inv);    
}    
    
template <typename T>    
std::pair<std::vector<T>, int> merge(std::vector<std::vector<T>>& array,    
                                     int cnt) {    
  std::vector<std::vector<int>> final_array;    
    
  if (array.size() % 2 > 0) array.push_back({});    
    
  for (int i = 0; i < array.size() - 1; i += 2) {    
    std::pair<std::vector<T>, int> res = sort_arrays(array[i], array[i + 1]);    
    
    cnt += res.second;    
    final_array.push_back(res.first);    
  }    
    
  if (final_array.size() == 1) return std::make_pair(final_array[0], cnt);    
    
  return merge(final_array, cnt);    
}    
    
template <typename T>    
std::pair<std::vector<T>, int> merge_sort(std::vector<T>& array) {    
  std::vector<std::vector<T>> single_array = split_array(array);    
  return merge(single_array, 0);    
}