题解 | #数组中的逆序对# 归并排序 ： 递归， 二分

class Solution {
private:
    const int kmod = 1000000007;
public:

    void merge_sort__(vector<int>& arr, vector<int>& tmp, int l, int r, int& ret)
    {
        if(l>=r)
        {
            return;
        }

        int mid = (r+l)/2;

        // 二分后 再分别 divide
        merge_sort__(arr, tmp, l, mid, ret);
        merge_sort__(arr, tmp, mid+1, r, ret);

        // 分完之后的 治 最底层是  前后半个区间里的 首两个元素的合并
        merge__(arr, tmp, l, r, mid, ret);
    }

    void merge__(vector<int>& arr, vector<int>& tmp, int l, int r, int mid, int& ret)
    {
        // ret 保存 逆序对数 取余的答案

        // 刚才提到在函数内部开辟额外空间的做法很不好。因为这样会涉及到频繁的构建 vector 和析构vector，所以比较好的做法是：直接在最外层开辟一个足够大的数组，然后传引用到函数。
        // vector<int> tmp(r-l+1); // 两部分的总长度
        int i = l, j = mid+1, k=0; // i 和 j各自从 首元素开始

        while(i<=mid && j<=r)
        {
            // 比较大小
            if(arr[i]<arr[j])
            {
                tmp[k++] = arr[i++];
            }
            else
            { // i<j 但元素值相反 是逆序
                tmp[k++] = arr[j++];
                // ret++;
                // miao  由于 [l, mid] [mid+1, r] 已经是各自有序的 所以当a[i]>a[j]
                // 那么从i 道mid 这 mid-i+1 计几个元素和j 都可构成逆序对
                ret += (mid-i+1);

                ret %= kmod;
            }
        }

        // 剩余的元素全放在tmp后面 这是指两半 元素不等的情况
        while(i<=mid)
        {
            tmp[k++] = arr[i++];
        }
        while(j<=r)
        {
            tmp[k++] = arr[j++];
        }

        //再赋值给 arr本身 才能保证每次归并 两部份都是有序

        for(int i=l, k=0; i<=r; ++i, ++k)
        {
            arr[i] = tmp[k]; // 注意这里 赋值回去时还在 arr[l,r] 内 但tmp 每次只是用了前(r-l+1)的地方  
        }

    }

    // 暴力枚举 会超时
    // 官解二： 归并排序的思想
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> tmp(n); //直接在这里开个中间变量 否则放在内部 还会超时
        int cnt = 0;

        merge_sort__(data, tmp, 0, n-1, cnt);
        
        return cnt;
        
    }
};