力扣315计算右侧小于当前元素的个数

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int>index,temp,tempindex,counts;
        index.resize(nums.size(),0);
        temp.resize(nums.size(),0);
        tempindex.resize(nums.size(),0);
        counts.resize(nums.size(),0);//需要记录下标的数组，用来保存下标。采用归并排序算法进行求解
        for(int i=0;i<nums.size();i++)index[i]=i;
        sort(nums,0,nums.size()-1,index,temp,tempindex,counts);
        return counts;
    }
    void sort(vector<int>&nums,int l,int r,vector<int>&index,vector<int>&temp,vector<int>&tempindex,vector<int>&counts){
        if(r==l)return;
        int mid = l + (r-l)/2;
        sort(nums,l,mid,index,temp,tempindex,counts);
        sort(nums,mid+1,r,index,temp,tempindex,counts);
        mergersort(nums,l,mid,r,index,temp,tempindex,counts);
    }
    void mergersort(vector<int>&nums,int l,int mid,int r,vector<int>&index,vector<int>&temp,vector<int>&tempindex,vector<int>&counts){
        int left = l,right=mid+1,cnt=0;
        while(left<=mid&&right<=r){
            if(nums[left]<=nums[right]){
                temp[cnt]=nums[left];
                tempindex[cnt]=index[left];
                counts[index[left]]+=right-mid-1;
                cnt++;
                left++;
            }
            else{
                temp[cnt] = nums[right];
                tempindex[cnt]=index[right];
                cnt++;
                right++;
            }
        }
        while(left<=mid){
            temp[cnt]=nums[left];
            tempindex[cnt]=index[left];
            counts[index[left]]+=right-mid-1;
            cnt++;
            left++;
        }
        while(right<=r){
            temp[cnt]=nums[right];
            tempindex[cnt]=index[right];
            right++;
            cnt++;
        }
        for(int n=0;n<r-l+1;n++){
            nums[n+l]=temp[n];
            index[n+l]=tempindex[n];
        }
    }
};