A21076. 在一个数组中，如果两个元素a[i]和a[j]满足 i < j 且 a[i] > a[j] ，则 a[i] 和 a[j]，则 a[i] 和 a[j] 是一个逆内的逆序对。下面代码可以正确统计数组 a 区间[l,r]内的逆序对总数。cnt = 0 def merge_count(a, l, m, r): global cnt i = l j = m + 1 while i <= m and j <=…

在一个数组中，如果两个元素a[i]和a[j]满足 i < j 且 a[i] > a[j] ，则 a[i] 和 a[j]，则 a[i] 和 a[j] 是一个逆内的逆序对。

下面代码可以正确统计数组 a 区间[l,r]内的逆序对总数。

cnt = 0

def merge_count(a, l, m, r):
    global cnt
    i = l
    j = m + 1

    while i <= m and j <= r:
        if a[i] <= a[j]:
            i += 1
        else:
            cnt += (m - i + 1)
            j += 1


if __name__ == "__main__":
    a = [2, 4, 1, 3]
    merge_count(a, 0, 1, 3)
    print(f"跨区间逆序对数量: {cnt}")