题目描述

blablabla

样例

# 逆序对的数量

def sort(data, l, r):
    if (l >= r):
        return 0
    mid = (l+r) // 2
    i=l
    j=mid+1
    res = []
    num = sort(data, l, mid) + sort(data, mid+1, r)
    while i<=mid and j<=r:
        if data[i] <= data[j]: #########稳定
            res.append(data[i])
            i += 1

        else:
            res.append(data[j])
            j += 1
            num += mid -i + 1    #######注意！
    res += data[i:mid+1]
    res += data[j:r+1]
    data[l:r+1] = res
    return num

if __name__ == "__main__":
    n = int(input())
    data = [int(x) for x in input().split()]
    l = 0
    r = n-1
    num = sort(data, l, r)
    print(num)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla