日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_5】D: Recursion / Divide and Conquer - The Number of Inversions

問題

反転数 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 反転数を求める問題.
  • バブルソートの要領で探すと {O(n^2)}になってTLEするので効率よく探す必要がある.
  • タイトルの通り, 分割統治法(マージソート)を活用することで {O(n log{n})}でカウントすることができる.
  • 反転数は, 対象データが格納されている配列を二分しLとRを作った時, 配列Rの各要素R[j]について, R[j]よりもあとに移動するようなLの要素は, (Lの要素数)-(Lの現在のインデックス)で求められる.

コード

#include <iostream>

using namespace std;

typedef long long ll;

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
#define INF 2000000000
#define int ll

ll n;
ll input[200001];
ll l[100002];
ll r[100002];

ll merge(int left, int right, int mid){
  rep(i, mid - left) l[i] = input[left + i];
  rep(i, right - mid) r[i] = input[mid + i];
  
  // 番兵
  l[mid -left] = r[right - mid] = INF;
  int l_idx, r_idx;
  ll cnt;
  l_idx = r_idx = 0;
  cnt = 0;
  REP(i, left, right){
    if(l[l_idx] <= r[r_idx]){
      input[i] = l[l_idx];
      l_idx++;
    }else{
      input[i] = r[r_idx];
      r_idx++;
      cnt += ((mid - left) - l_idx);
    }
  }
  return cnt;
}

ll mergeSort(int left, int right){
  if(right - left > 1){
    int mid = (right + left)/2;
    ll ret = mergeSort(left, mid);
    ret += mergeSort(mid, right);
    return (ret + merge(left, right, mid));
  }else{
    return 0;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  cin >> n;
  rep(i, n){
    cin >> input[i];
  }

  cout << mergeSort(0, n) << endl;
}

参考

www.slideshare.net