计算数组的小和

# -*- 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