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

在归并排序模版上增加一句

class Solution {
private:
    using ll = long long;
    ll mergeSort(vector<int>& nums, vector<int>& tmp, int low, int high) {
        if (low >= high) return 0;
        int mid = (low + high) >> 1;
        ll cnt = mergeSort(tmp, nums, low, mid) + mergeSort(tmp, nums, mid + 1, high);
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) {
                tmp[k] = nums[j++];
            } else if (j > high) {
                tmp[k] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                cnt += nums[i] * (high - j + 1); //增加的一句
                tmp[k] = nums[i++];
            } else {
                tmp[k] = nums[j++];
            }
        }
        return cnt;
    }

public:
    long long calArray(vector<int>& nums) {
        vector<int> tmp(nums);
        return mergeSort(nums, tmp, 0, nums.size() - 1);
    }
};