基础课学习笔记（汇总）{:target=”_blank”}

// 注意逆序对数量 int 存不下，要用 long long
#include <iostream>
#define int long long
using namespace std;
const int N = 100010;
int n, a[N], temp[N], res;
void mergesort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    mergesort(l, mid), mergesort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) temp[k++] = a[i++];
        // 增加一行代码: res += mid - i + 1;
        else temp[k++] = a[j++], res += mid - i + 1;
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = temp[i];
}
// 这里由于 define 了 int 为 long long
// 所以主函数用 signed main() 代替，跟 int main() 无差别
signed main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    mergesort(0, n - 1);
    cout << res << endl;
    return 0;
}