Python（分治算法）问题 F: 求逆序对

题目描述

给定一个序列a1,a2,…,an，如果存在iaj，那么我们称之为逆序对，求逆序对的数目。
注意：n<=10^5，ai<=10^5

输入

第一行为n,表示序列长度。
接下来的n行，第i+1行表示序列中的第i个数。

输出

所有逆序对总数。

样例输入

4
3
2
3
2

样例输出

3

解答（分治算法）：

def merge(a, lt, rt):
    mid = (lt + rt) // 2
    x = 0  # 统计逆序对
    tmp = [0] * (rt - lt + 1)
    li_1 = []
    i = lt  # 左区间起点
    j = mid + 1  # 右区间起点
    k = 0  # 表示第一个数后面的逆序对
    while mid >= i and j <= rt:
        if a[i] <= a[j]:
            tmp[k] = a[i]
            i += 1
        else:
            tmp[k] = a[j]
            j += 1
            x += mid - i + 1
            li_1.append(x)
        k += 1
    while mid >= i:
        tmp[k] = a[i]
        i += 1
        k += 1
    while rt >= j:
        tmp[k] = a[j]
        j += 1
        k += 1
    for i in range(k):
        a[lt + i] = tmp[i]
    return x


s = 0


def merge1(li, lt, rt):
    global s  # 全局变量s
    if rt > lt:  # lt==rt 表示只有一个数，退出
        mid = (lt + rt) // 2
        merge1(li, lt, mid)
        merge1(li, mid + 1, rt)
        s += (merge(li, lt, rt))
        return s


n = int(input())
li1 = []
for i in range(n):
    n1 = int(input())
    li1.append(n1)

print(merge1(li1, 0, len(li1) - 1))

答案不唯一，必定有更加优化的解法欢迎分享