在归并排序的基础上稍加修改即可

我们首先来看逆序对的定义在计算机科学中，逆序对指的是在一个数组中，满足以下条件的元素对：数组中的两个元素 $( (a_i, a_j) )$，其中 $( i < j $) 且 $( a_i > a_j )$。换句话说，逆序对是指在数组中前面的元素比后面的元素大。

再看我们归并排序的合并过程，$i$指针在左区间，$j$指针在右区间,一定满足$( i < j $)，其次，归并的时候由于左右区间均有单调性，所以当出现$( a_i > a_j )$的时候从$a_i$开始到左区间末尾$mid$一定都满足$( a_i > a_j $)，故逆序对的数量为$mid - i + 1$，即$i$到$mid$的区间长度。

#include <iostream>
typedef long long LL;
using namespace std;
constexpr int N = 1e5;
int n;
int a[N+50], t[N+50];//t是辅助数组
LL res;
LL merge_sort(int q[], int l, int r) {
  //递归操作（结束后，子区间内部都是相对有序的，所以需要后续的合并保证整体有序）
  if(l == r) return 0;
  int mid = (l + r) / 2;
  merge_sort(q, l, mid);
  merge_sort(q, mid + 1, r);
  //合并操作(用了双指针的思想，谁小就加谁，最小数的不仅满足剩下的全局最小，也满足当前区间的最小，
  //所以如果出现左右区间某一个被递归处理完的时候，另外一个区间的数字一定比处理的所有数都大，
  //故后面可以直接补上剩余的数字)
  int ti = l, i = l, j = mid + 1;
  while(i <= mid && j <= r) {
    if(q[i] <= q[j]) {
      t[ti++] = q[i++];
    }
    else {
      t[ti++] = q[j++];
      res += mid - i + 1;
    }
  }
  //哪个区间有剩余就处理剩下的部分
  while(i <= mid) {
    t[ti++] = q[i++];
  }
  while(j <= r) {
    t[ti++] = q[j++];
  }
  //拷贝至原数组
  for(int i = l; i <= r; ++i) {
    q[i] = t[i];
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  cout << merge_sort(a, 1, n) << "\n";
  return 0;
}