class Solution {
public:
    //归并思想，先算左边逆序数，再算右边逆序数，最后算出左右两边
    int merge(vector<int>& nums,int l,int r){
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums,l,mid) + merge(nums,mid + 1,r);
        //i,j 为指向左右序列的指针，统计左右的逆序数个数
        int i = l,j = mid + 1;
        vector<int > tmp;
        while(i <= mid && j <= r){
            //如果左边的数小于右边的数，左边的数后移动一位，否则j++，res += i - j + 1;
            if(nums[i] <= nums[j]) tmp.push_back(nums[i++]);
            else{
                res += mid - i + 1;
                tmp.push_back(nums[j++]);
            }

        }
        while(i <= mid) tmp.push_back(nums[i++]);
        while(j <= r) tmp.push_back(nums[j++]);
        i = l;
        for(auto x: tmp)   
            nums[i++] = x;
        return res;
    }

    int inversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size() - 1);
    }
};