P1750 求逆序对

逆序对问题可以用归并排序来解决。在归并排序的过程中，我们可以在合并两个有序数组的过程中，统计逆序对的个数。

具体来说，我们在合并两个有序数组时，先将它们分别按照从小到大的顺序排列，然后从前往后遍历这两个数组，每次取出较小的元素加入到合并后的数组中。如果取出的元素来自第一个数组，那么不会产生逆序对；如果来自第二个数组，那么产生的逆序对个数就是第一个数组中剩下的元素个数。

具体实现时，我们可以在归并排序的递归函数中添加一个参数，来记录逆序对的个数。每次合并两个有序数组时，将逆序对的个数加上第一个数组中剩余元素的个数即可。

时间复杂度为O(nlogn)。下面是代码实现：

#include <iostream>
#include <vector>

using namespace std;

int merge(vector<int>& nums, int left, int mid, int right, vector<int>& tmp) {
    int i = left, j = mid + 1, k = 0;
    int count = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
            count += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    for (i = 0; i < k; i++) {
        nums[left + i] = tmp[i];
    }
    return count;
}

int mergeSort(vector<int>& nums, int left, int right, vector<int>& tmp) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    int count = mergeSort(nums, left, mid, tmp) + mergeSort(nums, mid + 1, right, tmp);
    count += merge(nums, left, mid, right, tmp);
    return count;
}

int reversePairs(vector<int>& nums) {
    int n = nums.size();
    vector<int> tmp(n);
    return mergeSort(nums, 0, n - 1, tmp);
}

int main() {
    vector<int> nums = {7, 5, 6, 4};
    cout << reversePairs(nums) << endl; // expect 5
    return 0;
}