题解 | #数组中的逆序对#

#include <algorithm>
#include <type_traits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        size_t cnt = 0;
        auto merge = [&nums, &cnt](auto&& merge_, int l, int r) -> void {
            if(l + 1 == r or l == r) return;

            int len = r - l;
            int mid = (l + r) / 2;

            merge_(merge_, l, mid);
            merge_(merge_, mid, r);

            std::remove_reference_t<decltype(nums)> tmp;
            tmp.reserve(len);

            int pa = l, pb = mid;
            while(pa < mid and pb < r) {
                auto a = nums[pa];
                auto b = nums[pb];
                if (a <= b){
                    tmp.push_back(a);
                    ++ pa;
                } else {
                    tmp.push_back(b);
                    cnt += mid - pa;
                    ++ pb;
                }
            }
            
            for(; pa < mid; ++ pa) tmp.push_back(nums[pa]);
            for(; pb < r; ++ pb) tmp.push_back(nums[pb]);

            move(tmp.begin(), tmp.end(), nums.begin() + l);
        };

        merge(merge, 0, nums.size());
        return cnt % 1000000007;
    }
};