交易逆序对的总数

该题解使用了分治算法结合归并排序来寻找逆序对。首先，将数组分成左右两部分，递归地在每部分中找逆序对。在合并两部分的过程中，通过比较左右两部分的元素，统计跨越中点的逆序对的数量。如果左边元素大于右边元素，表明存在逆序对，并且逆序对的数量等于左边数组中从当前元素到中点的元素个数。

时间复杂度: O(n log n)

空间复杂度: O(n)

from typing import List


class Solution:
    result = 0  # 用于存储全局的逆序对个数

    def reversePairs(self, nums: List[int]) -> int:
        if not nums:
            return 0
        N = len(nums)
        if N == 1:
            return 0
        self.merge_count([0]*N, nums, 0, N-1)  # 初始化辅助数组并开始递归
        return self.result

    def merge_count(self, aux, a, lo, hi):
        if lo >= hi:
            return
        mid = (lo + hi) // 2
        self.merge_count(aux, a, lo, mid)  # 递归处理左半部分
        self.merge_count(aux, a, mid+1, hi)  # 递归处理右半部分
        self.merge(aux, a, lo, mid, hi)  # 合并两部分

    def merge(self, aux, a, lo, mid, hi):
        i = lo
        j = mid + 1
        for k in range(lo, hi + 1):
            aux[k] = a[k]  # 复制元素到辅助数组
        for k in range(lo, hi + 1):
            if i > mid:
                a[k] = aux[j]
                j += 1
            elif j > hi:
                a[k] = aux[i]
                i += 1
            elif aux[j] < aux[i]:
                a[k] = aux[j]
                j += 1
                self.result += mid-i+1  # 计算逆序对
            else:
                a[k] = aux[i]
                i += 1

if __name__ == '__main__':
    s = Solution()
    print(s.reversePairs([7,5,6,4]))