>>73 バブルソートの交換回数は a[i] > a[j] (i < j) なる要素対の数だから
それをマージソートしながら数えてやる．計算量 O(n log n)．
#include <iostream>
#include <vector>
using namespace std;
int bubble_count(const vector<int> &a) {
  int count = 0;
  int n = a.size() / 2;
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end);
    count += bubble_count(b);
    count += bubble_count(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i) {
      if (k == c.size())      a[i] = b[j++];
      else if (j == b.size()) a[i] = c[k++];
      else if (b[j] <= c[k])  a[i] = b[j++];
      else                  { a[i] = c[k++]; count += n/2 - j; }
    }
  }
  return count;
}