BM20　数组中的逆序对¶

中等通过率 17.44%python3核心代码模式样例通过牛客 AC数组

牛客原题　源码

讲解章节：分治的三步框架

一句话

自底向上归并排序，右半元素提前出队时一次性记账。

解题思路¶

这题考什么¶

把「统计逆序对」归约到归并排序的合并阶段。

设左半 a[i..mid) 与右半 a[j..hi) 各自已经有序，合并时比较 a[i] 与 a[j]：

a[i] <= a[j]   左边这个数不大于右边所有待出队的数，不产生逆序对
a[i] >  a[j]   a[j] 必须先出队。左半从 i 到 mid-1 的每个数都大于 a[j]，
               而它们在原数组里全都排在 a[j] 前面 —— 一次性贡献
               **mid - i** 个逆序对

每个「右半元素提前出队」的动作，代价恰好等于左半的剩余长度。分治的每一层清算的是「跨越左右半段」的逆序对，段内的留给下一层，因此各层相加不重不漏，就是总数。归并排序本身见排序。

实现取自底向上（bottom-up）而非递归：

width = 1, 2, 4, 8, ...
每轮把相邻两段长为 width 的有序块合并成长为 2 倍 width 的有序块

同一个问题也可以离散化后用树状数组从右往左统计「已出现且更小的个数」，复杂度同为 O(n log n)，见树状数组。

数据规模与复杂度¶

size <= 1e5，元素取值 0 到 1e9，时限 C/C++ 3 秒、其他语言 6 秒。归并是 O(n log n)：1e5 * 17 层约 1.7e6 次比较，Python 下零压力。两重循环枚举所有数对是 n 的平方的一半 = 5e9 次比较，Python 每秒千万级操作，差着三个数量级，必然超时。空间 O(n)：一条与原数组等长的缓冲区，全程复用不反复分配，符合题面的空间要求。

坑在哪¶

结果必须对 1000000007 取模。n = 1e5 完全逆序时答案约为 5e9， Python 整数不会溢出，所以漏掉取模不会报错，只会安静地输出一个判题机不认的大数。中间累加不取模是有意的：只在返回时取一次，逻辑最干净且不影响正确性。
记账的数量是 mid - i，即左半的剩余个数，不是 1。写成 1 就变成只统计相邻逆序对，样例 [1,2,3,4,5,6,7,0] 会输出 1 而不是 7。
比较写 a[i] <= a[j] 而不是 a[i] < a[j]：相等时让左边先出队才不会把相等的一对误记成逆序对。本题的输入描述保证没有相同数字，这一条在此处不起作用，但换到允许重复的题上，写成严格小于就是错的。
自底向上要处理尾部残段。n 不是 2 的幂时，最后一段可能凑不满一对，此时 mid >= hi 说明右半为空、该段已经有序，跳过即可；不跳过虽不会出错，但会白白多做一次整段的复制回写。
选自底向上的理由是省掉函数调用，不是怕爆栈：递归版深度只有约 17 层，远不到 Python 默认的一千层上限，但 Python 的函数调用开销很贵， n = 1e5 时递归版要多付出约 2e5 次调用。

样例复核¶

[1,2,3,4,5,6,7,0]。除了 0 之外的 7 个数都比它大且都排在它前面，其余数对本身升序，总数正好 7，与样例输出一致。

参考实现¶

solutions/nowcoder/BM20/sol.py
from typing import List, Optional


class Solution:
    def InversePairs(self, nums: List[int]) -> int:
        MOD = 1000000007                # 题面要求输出 P mod 1000000007
        n = len(nums)
        # 一个数以下不可能成对，提前退出省掉后面的缓冲区分配
        if n < 2:
            return 0

        a = list(nums)                  # 归并会重排元素，复制一份，不改动入参
        buf = [0] * n                   # 合并用的临时区，全程复用不反复分配
        total = 0
        # 自底向上：块宽 1、2、4 ... 逐层翻倍，每层把相邻两块并成一块
        width = 1
        while width < n:
            step = width * 2
            # [lo, mid) 与 [mid, hi) 是本轮要合并的两个有序块，都用 min 夹住防越界
            for lo in range(0, n, step):
                mid = min(lo + width, n)
                hi = min(lo + step, n)
                if mid >= hi:           # 尾部残段：右半为空，本段已有序
                    continue            # 跳过后省掉一次无谓的整段复制回写
                # i 走左半、j 走右半、k 是缓冲区写入位置
                i, j, k = lo, mid, lo
                while i < mid and j < hi:
                    # 相等时让左边先出队：相等不算逆序对，也保证归并的稳定性
                    if a[i] <= a[j]:
                        buf[k] = a[i]
                        i += 1
                    else:
                        # 左半从 i 到 mid-1 全都大于 a[j] 且排在它前面，一次记账
                        total += mid - i
                        buf[k] = a[j]
                        j += 1
                    k += 1
                # 收尾：一侧走完后另一侧原样搬过去，跨段逆序对已经数完
                while i < mid:              # 左半余量直接搬（不再有逆序对）
                    buf[k] = a[i]
                    i += 1
                    k += 1
                while j < hi:               # 右半余量同理
                    buf[k] = a[j]
                    j += 1
                    k += 1
                a[lo:hi] = buf[lo:hi]   # 把合并结果写回，供下一层使用
            width = step
        # 中间累加全程不取模（Python 整数无上限），返回前取一次即可
        return total % MOD

BM20 数组中的逆序对¶