计算右侧小于当前元素的个数(归并排序)_用r语言计算右侧小于当前元素的个数

### 解题思路

归并排序

### 代码

class Solution {
public:
    vector<int> res;
    vector<pair<int,int>> temp;
    vector<pair<int,int>> pairIdx;
    void mergeSort (vector<pair<int,int>>& nums,int l,int r){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        int p1=l,p2=mid+1,k=0;
        while(p1 <= mid && p2 <= r){
            if(nums[p1].first <= nums[p2].first){
                res[nums[p1].second] += p2-mid-1;
                temp[k++] = nums[p1++];
            }
            else temp[k++] = nums[p2++];
        }
        while(p1 <= mid){
            res[nums[p1].second] += p2-mid-1;
            temp[k++] = nums[p1++];
        }
        while(p2 <= r) temp[k++] = nums[p2++];
        for(int i = l,j=0;i <= r;i++,j++) nums[i] = temp[j];
    }
    vector<int> countSmaller(vector<int>& nums) {
        res = vector<int>(nums.size(),0);
        temp = vector<pair<int,int>>(nums.size());
        for(int i = 0; i < nums.size(); ++i) pairIdx.push_back({nums[i],i});
        mergeSort(pairIdx,0,nums.size()-1);
        return res;
    }
};