29458: 求逆序对数

merge sort, http://cs101.openjudge.cn/practice/29458/

给定长度为 n 数组 a

询问有多少个 1 <= i < j <= n，满足 a[i] > a[j]

输入

第一行一个数字 n。

第二行，一行 n 个数字，第 i 个数字表示 a[i](1 <= a[i] <= 10^9)。

输出

满足条件的 (i,j) 的对数。

样例输入

6
2 6 3 4 5 1

样例输出

提示

利用二分归并排序算法（分治）

对于70%的数据，n<=1000 对于100%的数据，n<=200000

python

def count_inversions(arr):
    # 辅助函数：归并排序并统计逆序对
    def merge_sort(arr):
        if len(arr) <= 1:
            return arr, 0
        
        mid = len(arr) // 2
        left, inv_left = merge_sort(arr[:mid])  # 对左半部分排序并统计逆序对
        right, inv_right = merge_sort(arr[mid:])  # 对右半部分排序并统计逆序对
        
        merged, inv_split = merge(left, right)  # 合并左右两部分并统计跨越的逆序对
        
        return merged, inv_left + inv_right + inv_split
    
    # 辅助函数：合并两个有序数组并统计跨越的逆序对
    def merge(left, right):
        merged = []
        i = j = inv_count = 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])
                inv_count += len(left) - i  # 左边剩余的元素都比 right[j] 大
                j += 1
        
        # 添加剩余的元素
        merged.extend(left[i:])
        merged.extend(right[j:])
        
        return merged, inv_count
    
    # 调用归并排序
    _, total_inversions = merge_sort(arr)
    return total_inversions

# 输入处理
n = int(input())
arr = list(map(int, input().split()))

# 输出结果
print(count_inversions(arr))

29458: 求逆序对数 ​

29458: 求逆序对数