【CF #790 H2. Maximum Crossings (Hard Version)】逆序对经典 + 偷懒调力扣api

求逆序对树（注意前面的等于后面的也算）
用归并排序，原理脑壳疼
直接调力扣接口
我负责输入输出

from typing import List


class Solution:
    def mergeSort(self, nums, tmp, l, r):
        if l >= r:
            return 0

        mid = (l + r) // 2
        inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r)
        i, j, pos = l, mid + 1, l
        while i <= mid and j <= r:
            if nums[i] < nums[j]: # little change
                tmp[pos] = nums[i]
                i += 1
                inv_count += (j - (mid + 1))
            else:
                tmp[pos] = nums[j]
                j += 1
            pos += 1
        for k in range(i, mid + 1):
            tmp[pos] = nums[k]
            inv_count += (j - (mid + 1))
            pos += 1
        for k in range(j, r + 1):
            tmp[pos] = nums[k]
            pos += 1
        nums[l:r+1] = tmp[l:r+1]
        return inv_count

    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        tmp = [0] * n
        return self.mergeSort(nums, tmp, 0, n - 1)


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    temp = Solution()
    print(temp.reversePairs(a))

直呼接口大法好
注意python如果wa
要采用python3.8.10和python3.7.10都试试
编译器还分快慢 无语子