题目描述

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

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

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

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

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

数据范围
1≤n≤100000

样例

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

算法1

归并排序

分治，归并排序
1.将整个区间一分为二，l,mid,r
2.递归排序[l,mid],[mid+1,r]
3.归并，将左右2个有序序列合并成一个有序序列

时间复杂度

nlog(n)

参考文献

python 代码

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=0
    i = l
    j = mid+1
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            tmp[k] = q[i]
            i+=1
        else:
            tmp[k] = q[j]
            res += mid-i+1      #关键公式
            j+=1
        k+=1
    while i<=mid:
        tmp[k]=q[i]
        i+=1
        k+=1
    while j <= r:
        tmp[k]=q[j]
        j+=1
        k+=1
    j=0
    for i in range(l,r+1):
        q[i] = tmp[j]
        j+=1
    return res


if __name__ == "__main__":
    n = int(input())
    q = list(map(int,input().split()))
    N = 100010
    tmp = [0]*N
    print(merge_sort(q,0,n-1))