题意

题面算法每轮先从左向右冒泡，再从右向左冒泡，最后检查是否有逆序对。求进入循环并输出 moo 的次数。

思路

直接模拟双向冒泡是 $O(n^2)$ 的，N=10^5 不可行。必须找到一个不模拟就能算出轮数的度量。

一句话本质

把动态的冒泡过程转化为静态的"错位统计"——双向冒泡的轮数等于所有切割位置中，"左边误入多少不该在的元素"的最大值，用稳定排序与差分一次求出。

深度追究：自问自答

直接模拟双向冒泡为何不能接受？

$N = 10^5$，模拟一轮双向冒泡是 $O(N)$，最坏需要 $O(N)$ 轮，总复杂度 $O(N^2)$。必须找到一个不模拟就能算出轮数的度量。

排序成功后，任意位置 k 的左边应该是什么？

位置 $0 \dots k$ 必须装下最小的 $k+1$ 个元素（含相同值时按稳定排序顺序）。这是排序的定义，不需要灵感。

初始数组里，位置 k 这条"分界线"出了什么问题？

左边混进了几个排好序后应该出现在 k 右边的元素？等价地，右边少了几个应该出现在 k 左边的元素？两者数量永远相等，记为 $m_k$。

双向冒泡每一轮，对固定的 k 做了什么？

正向扫描把"太大"的元素往右推，逆向扫描把"太小"的元素往左拉。但同一轮正向扫描在越过位置 $k$ 时，最多只让 1 个元素从左侧穿过 k 到右侧——因为指针扫过去后不会回头。逆向扫描类似地一次只让 1 个元素穿过 k 回左侧。两个方向合起来，每一轮最多消掉 1 个错位。

那么整张数组需要多少轮？

每个 $k$ 至少要 $m_k$ 轮；最拥挤的那条边界决定全局轮数：

取 $\max$ 为 1 是因为已有序时循环仍要进入一次打印 moo。

元素有重复值时怎么办？

必须用稳定排序——值相同时按原下标作为第二关键字。否则会把本不需要跨越边界的相同值也算成错位，导致 $m_k$ 被高估。

怎样在 $O(N \log N)$ 内算出所有 $m_k$？

对每个向右跨越位置 k 的元素，它在 $k \in [\text{原位置}+1,\;\text{排好位置}]$ 上贡献 1。这是一段连续区间，用差分数组做区间 $+1$，前缀和还原后取最大值即可。

关键卡点

真正的概念卡点不在"差分"也不在"$O(N \log N)$"，而在这一句：“每一轮正向扫描最多只让 1 个元素穿过某条分界线”。一旦接受这个观察，问题就退化为静态计数；所有其他都是实现细节。

思维映射

人脑推理：从"分界点"而不是"边界"出发

"跨越边界"是事后总结出的干净概念。比赛中没人一开始就想到这个，但可以从更自然的问题起步。

第 1 步：排序成功后，每个位置 k 的左边应该是什么？

排序后，位置 k 的左边（$0 \dots k$）必须是最小的 $k+1$ 个元素。这是排序的定义，不需要灵感。

第 2 步：初始数组里，这个"分界线"出了什么问题？

选一个位置 k，扫一眼初始数组：左边 $0 \dots k$ 里有没有排好序后应该出现在 k 右边的元素？换句话说，左边混进了多少"太大"的。

以样例 [1,8,5,3,2] 为例，选 k=2：左边 3 个坑位，排好后应是 [1,2,3]。但实际上左边是 [1,8,5]，混进了 5 和 8 两个"太大"的，少塞了 2 和 3 两个"太小"的。k=2 这条分界线出了 2 个错位。

第 3 步：冒泡的每轮在干什么？

正向扫描把"太大"的元素往右推，逆向扫描把"太小"的元素往左拉。对于分界点 k，正向扫描要做的就是把不该在左边的元素送出去。

第 4 步：一回合能送出去几个？

纸上演算——选一个 k，追踪第一轮正向扫描。你会发现：左边那些"太大"的元素里，只有最大的那个能一口气冲过 k，其余的被它挡在后面（指针已经扫过去，不会回头）。

所以每轮至多消掉一个错位。如果 k 处有 $m$ 个"太大"元素，就需要至少 $m$ 轮。

第 5 步：答案是所有分界点中最糟糕的那个。

对每个 k 统计"左边混进了几个不该在的元素"，取最大值——这就是轮数。写成代码时才意识到：“哦，这不就是在统计 k+1 这条边界上有几个元素要跨过去么。“但推理起点是"分界点左边的错位元素数”，这个不需要灵感，只需要问"排序成功后这里应该长什么样”。

热身：纯冒泡怎么算？

先退一步，看题目中的第一个代码（纯正向冒泡）。以样例 [1,8,5,3,2] 稳定排序后各元素的位置：

纯冒泡只有正向扫描。大元素可以一口气向右走很远（8 一轮冲到最右），但小元素向左每轮至多挪 1 位——扫描指针一路向右不再回头，小元素被挤到前一位后，指针已经过它了，不会在同一轮再处理它。

1
2
3
4第 1 轮: 2 从位置 4 → 位置 3
第 2 轮: 2 从位置 3 → 位置 2
第 3 轮: 2 从位置 2 → 位置 1 ✓ 归位
第 4 轮: 进入循环，无交换，打印 moo 后退出

纯冒泡的答案 = max(左移距离) + 1。+1 是最后一次确认有序仍要打印的 moo。样例中 max 左移 = 3，答案 = 4。

双向冒泡：瓶颈从"个体"变成"边界"

双向冒泡多了一个逆向扫描，小元素也能一口气向左走很远了。纯冒泡的 max(左移距离) 不再适用。

关键转变：不再关注"哪个元素最慢"，而是关注哪个位置最拥挤。

画一下"边界"——就是数组相邻元素之间的缝隙。样例 [1,8,5,3,2] 有 N+1=6 条边界：

1
2
3
4索引:   0      1      2      3      4
     [ 1 ]  [ 8 ]  [ 5 ]  [ 3 ]  [ 2 ]
      ^      ^      ^      ^      ^      ^
    边界0   边界1   边界2   边界3   边界4   边界5

边界 b 的左边是索引 $0 \dots b-1$，右边是索引 $b \dots N-1$。

谁需要跨越哪条边界？

稳定排序后，看每个元素需要向右跨越哪几条边界（向左的对称相等，后面解释）：

元素 5 从位置 2 到 3，跨过一条缝（边界3）；元素 8 从位置 1 到 4，跨过三条缝（边界2,3,4）。

统计每条边界有几个元素要跨过去：

1
2边界0: 0   边界1: 0   边界2: 1（8）
边界3: 2（5和8）      边界4: 1（8）  边界5: 0

最拥挤的是边界3，有 2 个元素等着跨。答案就是 2。

为什么边界3 上的 2 个元素不能一轮跨完？

看第 1 轮正向扫描发生了什么：

1
2
3
4
5[1, 8, 5, 3, 2]
       ↑ i=1: 8>5 交换 → 8 换到位置2
       ↑ i=2: 8>3 交换 → 8 换到位置3（8 跨过了边界3！）
       ↑ i=3: 8>2 交换 → 8 换到位置4
正向后: [1, 5, 3, 2, 8]

8 一口气跨过了边界3。但 5 呢？当正向扫描到 5 的时候，指针已经在 8 后面了，8 冲过去后指针跟着过去了，不会回头。所以这轮正向扫描里，5 待在原地没动。

逆向扫描后第 1 轮结束：[1, 2, 5, 3, 8]。5 仍然在边界3 的左边。第 2 轮正向扫描 5 才跨过去：[1,2,3,5,8]。

规律：每轮正向扫描，一条边界至多放一个元素过去——最大的那个会挤在前面挡住小的。所以边界3 上有 2 个元素等着，必须 2 轮。

为什么不用管向左跨越？

以边界3 为例：左边 3 个坑位（索引 0~2），排好后应该是 [1,2,3]。实际上左边有 5 和 8 占了不该占的位置，所以有 2 个正确元素（2 和 3）"被困在"右边。右边少了多少个正确元素 = 左边多塞了多少个错误元素，两边数量永远相等。所以只统计向右的就行。

用差分快速算出最拥挤边界

对于每个需要向右跨越的元素，它跨越的边界区间是 [原位置+1, 排好位置]。这是连续的一段，用差分数组标记区间加一：

1
2
3
4# 原位置 2 → 排好 3, 跨越 边界[3,3]
diff[3] += 1; diff[4] -= 1
# 原位置 1 → 排好 4, 跨越 边界[2,4]
diff[2] += 1; diff[5] -= 1

前缀和还原后取最大值，就是最拥挤边界的跨越数。

答案 = max(1, 最拥挤边界的跨越数)，至少为 1 是因为已经有序时循环仍会进入一次。

纯冒泡与双向冒泡的公式对比

Python 知识

• sorted(range(n), key=lambda i: (values[i], i)) 明确实现按值、原下标的稳定次序。
• int.bit_count 等技巧不需要出现在正解中；位置跨越用普通差分更直接。
• max(accumulate(difference)) 把差分还原和求最大值连在一起。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17import sys
from itertools import accumulate


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
values = [next(data) for _ in range(n)]
difference = [0] * (n + 1)

for sorted_position, original_position in enumerate(
    sorted(range(n), key=lambda i: (values[i], i))
):
    if original_position < sorted_position:
        difference[original_position + 1] += 1
        difference[sorted_position + 1] -= 1

print(max(1, max(accumulate(difference))))

复杂度

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

总结

无需模拟冒泡排序；排序后的位移把"多少轮"转成"最多有多少元素跨过同一边界"。