1. 求倒置数 【问题描述】数组A【0，...，n-1】是一个n个不同整数数构成的数组。如果i<j,但是A[i]〉A[j]，则这对元素（A[i]，A[j]）被称为一个倒置（inversion）。设计一个O（nlogn）算法来计算数组中的倒置数量 【输入形式】输入两行，第一行输入元素的个数n，第二行输入n个数据（中间用一个空格隔开）； 【输出形式】输出一个整数，即逆置数的个数； 【样例输入1】 8 2 3 8 9 1 4 5 7 【样例输出1】 10 【样例输入2】 2 21 7 【样例输出2】 1 【样例说明】 【评分标准】

以下是求倒置数的Python代码实现：

def merge_sort(nums):
    if len(nums) <= 1:
        return nums, 0
    mid = len(nums) // 2
    left, left_count = merge_sort(nums[:mid])
    right, right_count = merge_sort(nums[mid:])
    merged, cross_count = merge(left, right)
    return merged, left_count + right_count + cross_count

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    count = 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
            count += len(left) - left_idx
    result.extend(left[left_idx:])
    result.extend(right[right_idx:])
    return result, count

n = int(input())
nums = list(map(int, input().split()))
_, count = merge_sort(nums)
print(count)

首先，我们定义了一个归并排序函数 `merge_sort`，它会返回排好序的列表以及倒置数。

在归并排序中，我们将列表分成两半，对每一半进行递归排序，并将排序后的两个列表合并。在合并的过程中，我们统计跨越两个列表的倒置数。

最后，我们读入输入的数组，调用 `merge_sort` 函数并输出倒置数。

该算法的时间复杂度为O(nlogn)，符合题目要求。