计算数组的小和

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return long长整型
     */
    long long calArray(vector<int>& nums) {
        // 时间复杂度O(NlogN)，空间复杂度O(N)
        return mergeSort(nums, 0, nums.size() - 1);
    }
    long long mergeSort(vector<int> &nums, int left, int right) {
        if (left >= right) return 0;
        int middle = left + ((right - left) >> 1);
        return mergeSort(nums, left, middle) + 
            mergeSort(nums, middle + 1, right) + 
            merge(nums, left, middle, right);
    }
    long long merge(vector<int> &nums, int left, int middle, int right) {
        int tmp[right - left + 1];
        int i = left, j = middle + 1, k = 0;
        long long res = 0;
        while (i <= middle && j <= right) {
            res += nums[i] <= nums[j] ? (right - j + 1) * nums[i] : 0;
            tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= middle) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];
        for (k = 0; k < right - left + 1; ++k) nums[left + k] = tmp[k];
        return res;
    }
};

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return long长整型
 */
const Max = 100001
var help = make([]int,Max)

func calArray( nums []int ) int64 {
	if len(nums)==1 || len(nums)==0{
		return 0
	}
    left,right:= 0,len(nums)-1
	mid := (left + right) >> 1
	return calArray(nums[left:mid+1]) + calArray(nums[mid+1:right+1]) + merge(nums,left, mid, right)
}

func merge(arr []int,left, mid, right int) int64 {
	var ans int64
	// 默认右边基本大于左边，计算的公式如下
	// 在遍历右边的时候，依次遍历左边，若左侧小于等于右侧的数，则相加，否则不加
	// 如 1 3 5 | 2 4 6
	// 对2来说，只有1小于，sum=1,ans=1
	// 对4来说，右1,3小于，sum=4,ans=5
	// 对6来说，有1,3,5小于，sum=9,ans=14
	// 所以返回的merge为14
	for i, j, sum := left, mid+1, 0; j <= right; j++ {
		for i <= mid && arr[i] <= arr[j] {
			sum += arr[i]
			i++
		}
		ans += int64(sum)
	}
	index, lindex, rindex := left, left, mid+1
	for lindex <= mid && rindex <= right {
		if arr[lindex] <= arr[rindex] {
			help[index] = arr[lindex]
			index++
            lindex++
		} else {
			help[index] = arr[rindex]
			index++
            rindex++
		}
	}

	for lindex <= mid {
		help[index] = arr[lindex]
		index++
		lindex++
	}
	for rindex <= right {
		help[index] = arr[rindex]
		index++
		rindex++
	}
	for i := left; i <= right; i++ {
		arr[i] = help[i]
	}

	return ans
}

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return long长整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/6dca0ebd48f94b4296fc11949e3a91b8?tpId=196&tqId=40415&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=2&tags=&title=
    借鉴：
        大神：？？？也能被占用，爷服了
    算法：
        本题与 NC188 数组中的逆序对 有些类似，属于同一类题目，都是基于归并排序的思想，在merge的时候，进行计算。
        核心思想是：
            在merge的时候，如果nums[l] <= nums[r]，说明[r, right]区间内的所有元素都大于等于nums[l]，nums[l]需要累加right - r + 1次
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def calArray(self, nums):
        # write code here
        def mergeSort(left, right):
            if left >= right:
                return 0
            mid = left + ((right - left) >> 1)
            return mergeSort(left, mid) + mergeSort(mid + 1, right) + merge(left, mid, right)

        def merge(left, mid, right):
            L = right - left + 1
            tmpNums = [0] * L

            l, r, idx, ans = left, mid + 1, 0, 0
            while l <= mid and r <= right:
                if nums[l] <= nums[r]:
                    ans += (right - r + 1) * nums[l]
                    tmpNums[idx] = nums[l]
                    l += 1
                else:
                    tmpNums[idx] = nums[r]
                    r += 1
                idx += 1

            while l <= mid:
                tmpNums[idx] = nums[l]
                l += 1
                idx += 1

            while r <= right:
                tmpNums[idx] = nums[r]
                r += 1
                idx += 1

            for i in range(L):
                nums[left + i] = tmpNums[i]

            return ans

        n = len(nums)

        return mergeSort(0, n - 1)


if __name__ == "__main__":
    sol = Solution()

    nums = [1, 3, 5, 2, 4, 6]

    # nums = [1]

    res = sol.calArray(nums)

    print res