UVa299 Train Swapping

解法
バブルソートの交換回数（反転数）を求める。
バブルソートして求めるか、あるいはBITするかマージソートするかすればよい。
以下は BIT のコード。

#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

class BIT {
private:
  
  vector<int> bit;
  int size;
  
public:
  
  BIT(int n) : size(n)
  {
    bit.resize(n+1);
  }
  
  int sum(int i) {
    int s = 0;
    while(i > 0) {
      s += bit[i];
      i -= i & -i;
    }
    return s;
  }
  
  void add(int i, int x) {
    while(i <= size) {
      bit[i] += x;
      i += i & -i;
    }
  }
};

ll swapNumber(int *a, int N) {
  ll ret = 0;
  BIT b(N);
  rep(i, N) {
    ret += i - b.sum(a[i]);
    b.add(a[i], 1);
  }
  return ret;
}


int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    int N; cin >> N;
    int a[N];
    rep(i, N) {
      cin >> a[i];
    }
    cout << "Optimal train swapping takes "
         << swapNumber(a, N)
         << " swaps.\n";
  }
  
  return 0;
}