题意

求数组中的逆序对的数量。

分析

这题是以归并排序为载体的分治算法的应用。
把整个数组一分为二，逆序对出现的情况可能有三种，一种是两个数都在左半区间，一种是两个数都在右半区间，还有一种是分别处于两个区间。
只要把这三种情况都计算出来，就可以得到答案。
注意到前两种情况(都在左半边或者都在右半边)都可以递归解决，因此我们只需要考虑最后一种情况。
考虑在归并排序的骨架中，在哪里可以加入计数语句来算这种情况：在把后半个有序数组中的元素加入答案数组时，这个元素和前半个数组中还没加入答案数组的元素都构成逆序队，有 mid - i + 1 个。

class Solution {
public:
    int inversePairs(vector<int>& nums) {
        vector<int> tmp;
        tmp.resize(nums.size());
        return countInsersion(nums, 0, nums.size()-1, tmp);
    }

    int countInsersion(vector<int>& nums, int l, int r, vector<int>& tmp){
        if(l >= r)return 0;
        int mid = l+r>>1;
        int left_count = countInsersion(nums, l, mid, tmp);
        int right_count = countInsersion(nums, mid+1, r, tmp);
        int i = l, j = mid+1, k = 0;
        int cross_count = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]){
                tmp[k++] = nums[i++];
            }else {
                tmp[k++] = nums[j++];
                cross_count += mid - i + 1;
            }
        }
        while(i <= mid)tmp[k++] = nums[i ++];
        while(j <= r)tmp[k++] = nums[j++];
        for(i = l, k = 0; i <= r; i ++, k ++){
            nums[i] = tmp[k];
        }

        return left_count + right_count + cross_count;
    }
};