2-归并排序

#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010;
 
int n;
 
int q[N];
int tmp[N];
 
LL merge_sort(int l, int r) {
  if (l >= r)
    return 0;
 
  // 归并
  int mid = l + r >> 1;
  LL ans = merge_sort(l, mid) + merge_sort(mid + 1, r);
  int i = l, j = mid + 1, k = 0;
  while (i <= mid && j <= r) {
    if (q[i] <= q[j])
      tmp[k++] = q[i++];
    else {
      ans += mid - i + 1;
      tmp[k++] = q[j++];
    }
  }
  // 扫尾
  while (i <= mid) {
    tmp[k++] = q[i++];
  }
  while (j <= r) {
    tmp[k++] = q[j++];
  }
 
  // 回归
  for (int i = l, j = 0; i <= r; i++, j++) {
    q[i] = tmp[j];
  }
  return ans;
}
 
int main() {
  cin >> n;
 
  for (int i = 0; i < n; i++)
    cin >> q[i];
 
  cout << merge_sort(0, n - 1) << endl;
  return 0;
}