p1750 求逆序对

求逆序对是一个经典的问题，可以使用归并排序的思想来解决。具体来说，对于一个数组 $a$，我们可以将其分为左右两个子数组 $a_1$ 和 $a_2$，然后分别递归地求解 $a_1$ 和 $a_2$ 的逆序对个数，最后再计算 $a_1$ 和 $a_2$ 之间的逆序对个数，并将 $a_1$ 和 $a_2$ 合并成一个有序的数组。

下面是一个基于归并排序的求逆序对的示例代码：

def merge_sort(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cnt1 = merge_sort(a[:mid])
    right, cnt2 = merge_sort(a[mid:])
    merged, cnt3 = merge(left, right)
    return merged, cnt1 + cnt2 + cnt3

def merge(left, right):
    i, j = 0, 0
    merged = []
    cnt = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            cnt += len(left) - i
    merged += left[i:]
    merged += right[j:]
    return merged, cnt

其中，`merge_sort` 函数用于对数组进行归并排序，并返回排序后的数组和逆序对个数。`merge` 函数用于合并两个有序的数组，并计算它们之间的逆序对个数。

使用示例：

a = [3, 1, 4, 2, 5]
cnt = merge_sort(a)[1]
print(cnt)  # 输出 4

上述代码的时间复杂度为 $O(n\log n)$，其中 $n$ 是数组的长度。