A0990 车厢重组

#include <bits/stdc++.h>
using namespace std;

// 归并排序统计逆序对：左半段与右半段合并时，
// 右半段的元素若小于左半段当前元素，则左半段剩下的元素都与它构成逆序对
long long mergeCount(vector<int> &a, vector<int> &tmp, int l, int r) {
    if (r - l <= 1) return 0;
    int mid = l + (r - l) / 2;
    long long ans = mergeCount(a, tmp, l, mid) + mergeCount(a, tmp, mid, r);

    int i = l, j = mid, k = l;
    while (i < mid && j < r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            ans += mid - i;   // 左半段剩下的 mid - i 个元素都比它大
        }
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int t = l; t < r; t++) a[t] = tmp[t];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> a(N), tmp(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    cout << mergeCount(a, tmp, 0, N) << '\n';
    return 0;
}