4392: GESP C++ 六级 4小杨的握手问题202309

#include <iostream>
using namespace std;
int num[300000];
int tmp[300000];
long long merge(int l, int r) {
    if (l + 1 == r)
        return 0;
    int m = (l + r) / 2;
    long long res = merge(l, m) + merge(m, r);
    for (int i = l, j = m, k = l; k < r; k++) {
        if (j == r || (i < m && num[i] > num[j])) {
            tmp[k] = num[i];
        i++;
        } else {
            tmp[k] = num[j];
        j++;
        res += m - i;
        }
    }
    for (int k = l; k < r; k++)
        num[k] = tmp[k];
    return res;
}
int main() {
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    cout << merge(0, n) << endl;
    return 0;
}