Inversion Couting

countinv.cpp

// Very simple Inversion Counting based on a merge sort
// by cf/cebolinha
#include <bits/stdc++.h>
using namespace std;

#define int long long

int count_inversions(vector<int> &v) {
  if (v.size() == 1) return 0;

  // Divide v into two vectors - Left and Right
  vector<int> L, R;
  for (int i = 0; i < v.size()/2; i++) L.push_back(v[i]);
  for (int i = v.size()/2; i < v.size(); i++) R.push_back(v[i]);

  int inversions = 0;
  inversions += count_inversions(L);
  inversions += count_inversions(R);

  int Li = 0, Ri = 0;
  for (int i = 0; i < v.size(); i++) {
    if (Li == L.size()) v[i] = R[Ri++], inversions += L.size()-Li;
    else if (Ri == R.size()) v[i] = L[Li++];
    // WARNING: this next line can be either < or <= depending on the problem
    else if (L[Li] <= R[Ri]) v[i] = L[Li++];
    else v[i] = R[Ri++], inversions += L.size()-Li;
  }
  return inversions;
}

signed main() {
  int n; cin >> n;

  vector<int> v;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    v.push_back(x);
  }

  cout << count_inversions(v) << endl;
}