NC15163 逆序数

采用归并排序的思想
在对两个排好序的区间进行合并时，如果左边区间的数大于右边区间的数那么就出现了逆序对，计算一下从这个数的位置到区间最后还有几个数，这些数都是可以和右区间的数组成逆序对的。然后就看代码吧

#include <iostream>
using namespace std;
const int maxn = 100010;
int arr[maxn];
int nums[maxn];
long long  res = 0;
void merge(int l, int mid, int r) {
    int p1 = l;
    int p2 = mid + 1;
    for (int i = l; i <= r; i++) {
        if ((p1 <= mid) && ((p2 > r) || arr[p1] <= arr[p2])) {
            nums[i] = arr[p1];
            p1++;
        }
        else {
            nums[i] = arr[p2];
            p2++;
            res += mid - p1 + 1;//从这个数的位置到区间最后还有几个数
        }
    }
    for (int i = l; i <= r; i++) {
        arr[i] = nums[i];
    }

}
void erfen(int l, int r) {
    int mid = (l + r) / 2;
    if (l < r) {
        erfen(l, mid);
        erfen(mid + 1, r);
    }
    merge(l, mid, r);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    erfen(0, n - 1);
    cout << res;
}