题解 | #计算数组的小和#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return long长整型
     */
    long long Merge(vector<int>& nums,int l,int mid,int r,vector<int> &refArr)
    {    
        long long  ans=0;
        // for(int i=mid+1;i<=r;i++)
        // {
        //    int res=0;
        //    int j=l;
        //    while(j<=mid&&nums[j]<=nums[i])
        //    {
        //      res+=nums[j++];
        //    }
        //    ans+=res;
        // }   
        int lpos=l;
        int rpos=mid+1;
        int i=l;
        while(lpos<=mid&&rpos<=r)
        {
            //2 6 7 7 | 4 5 6 9
            //(r-rpos+1)*nums[lpos]
            //如果2<4 那么4后面的所有数都比2大，直接用比2大的个数乘以2，就是这一轮比较里面2所能贡献的小和。
            ans+=nums[lpos]<=nums[rpos]?(r-rpos+1)*nums[lpos]:0;
            refArr[i++]=nums[lpos]<=nums[rpos]?nums[lpos++]:nums[rpos++];
        }
        while(lpos<=mid)
        {
            refArr[i++]=nums[lpos++];
        }
        while(rpos<=r)
        {
            refArr[i++]=nums[rpos++];
        }
        for(int j=l;j<=r;j++)
        {
            nums[j]=refArr[j];
        }
        return ans;
    }

    long long smallSum(vector<int> &nums,int l,int r,vector<int> &refArr)
    {
        if(l==r) return 0;
        int mid=l+(r-l)/2;
        //左区间+右区间+左跨右区间
        return smallSum(nums,l,mid,refArr)+smallSum(nums,mid+1,r,refArr)+Merge(nums,l,mid,r,refArr);
    }

    long long calArray(vector<int>& nums) {
        // write code here
        vector<int> refArr(nums.size()+1);//辅助数组
        return smallSum(nums,0,nums.size()-1,refArr);
    }
};