题目描述

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000

样例

输入样例：
6
2 3 4 5 6 1
输出样例：
5

算法1

(归并) $O(nlog(n))$

比如在[3,4,1,2]中q[0]>q[2], 则q[0],q[1]都与q[2]成逆序对, 而q[mid]与q[i]有mid-i+1个数字，因此逆序对增加mid-i+1

Python 代码

n = int(input())
seq = list(map(int, input().split()))

def merge_sort(q, l, r):
    if l >= r: 
        return 0
    mid = (l + r) //2
    res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r)
    k, i, j = 0, l, mid + 1
    while i <= mid and j <= r:
        if q[i] <= q[j]:
            tmp[k] = q[i]
            k += 1
            i += 1
        else:
            res += mid - i + 1
            tmp[k] = q[j]
            k += 1
            j += 1
    while i <= mid:
        tmp[k] = q[i]
        k += 1
        i += 1
    while j <= r:
        tmp[k] = q[j]
        k += 1
        j += 1
    i, j = l, 0 
    while i <= r:
        q[i] = tmp[j]
        i += 1
        j += 1
    return res
tmp = [0] * n
print(merge_sort(seq, 0, n-1))