転倒数を求める問題を解きました。バブルソートの交換回数を数えることによっても求めることができますが、より高速なマージソートを用いた解法を実装します。

問題

次の問題を解きます。

考え方

マージソートを知っているものとします。

基本的なアイディアは、２つの部分列をマージするときに、順序が逆になっている数の組み合わせの数を数え、足し上げていくというものです。
左右の部分列の要素を先頭から順に比較し、小さいものをソート先の配列に格納するのがマージの手順です。右の部分列の要素の方が左の部分列の要素よりも小さいとき、左の部分列の要素のうち残されているものの数をカウントします。

解答例

#include<iostream>
using namespace std;

typedef long long ll;
const int N = 200000;
const int INFTY = 1000000001;


ll merge(int left, int mid, int right, int A[]) {
  ll cnt = 0;
  int i, j, k, n1, n2, *L, *R;
  
  n1 = mid - left;
  n2 = right - mid;
  L = new int[n1+1];
  R = new int[n2+1];

  for (i = 0; i < n1; i++) L[i] = A[left+i];
  for (i = 0; i < n2; i++) R[i] = A[mid+i];
  L[n1] = R[n2] = INFTY;

  j = k = 0;
  for (i = left; i < right; i++) {
    if (L[j] <= R[k]) {
      A[i] = L[j++];
    } else {
      A[i] = R[k++];
      cnt += n1 - j;
    }
  }

  delete [] L;
  delete [] R;

  return cnt;
}

ll merge_sort(int left, int right, int A[]) {
  if (left + 1 < right) {
    ll cnt1, cnt2, cnt3;
    int mid = (left + right) / 2;
    cnt1 = merge_sort(left, mid, A);
    cnt2 = merge_sort(mid, right, A);
    cnt3 = merge(left, mid, right, A);
    return cnt1 + cnt2 + cnt3;
  } else {
    return 0;
  }
}
  

int main() {
  int n;
  int A[N];

  cin >> n;
  for (int i = 0; i < n; i++) cin >> A[i];

  ll cnt = merge_sort(0, n, A);

  cout << cnt << endl;

  return 0;
}