題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P4375 [USACO18OPEN] Out of Sorts G

Problem Statement

題目簡述

奶牛 Bessie 正在學習演算法，其中她最喜歡的是泡沫排序。她原本的程式會在每一輪由左到右掃描陣列，若相鄰兩項順序錯誤就交換；每進入一輪迴圈時，程式都會輸出一次 moo。

Bessie 發現，在一般泡沫排序中，較大的元素很快會被推到陣列尾端，但較小的元素往前移動很慢。於是她修改程式，讓每一輪先由左到右掃描一次，再由右到左掃描一次，最後再檢查陣列是否已經排序完成。

給定初始陣列，請預測修改後的程式會輸出幾次 moo。

Constraints

約束條件

  • 1≤N≤1051 \le N \le 10^5
  • 0≤Ai≤1090 \le A_i \le 10^9
  • 輸入資料不保證互不相同

思路：轉化為分界線跨越問題

1. 觀察雙向泡沫排序的本質

題目要求計算修改後的雙向泡沫排序會執行幾輪。若直接模擬，最壞時間複雜度為 O(N2)\mathcal{O}(N^2)，無法通過 N=105N = 10^5 的測資。因此，我們必須挖掘排序過程中的不變量或規律。

在一輪雙向掃描中：

  • 由左至右掃描：會將目前未歸位的最大元素一路往右推。
  • 由右至左掃描：會將目前未歸位的最小元素一路往左推。
一輪掃描對陣列的「無序程度」有什麼具體影響？

想像在陣列的第 ii 個位置和第 i+1i+1 個位置之間畫一條分界線。
如果有元素原本在分界線左側，但排序後應該在右側，我們稱之為「需要向右跨越的元素」。
每一輪的「由左至右掃描」，必然會將左側最大的一個元素帶過這條分界線（如果左側還有該去右側的元素）。同理，「由右至左掃描」也會帶一個元素向左跨越。
因此，每一輪掃描，都會讓每條分界線需要跨越的元素數量減少 1。

2. 轉化為統計最大跨界數量

基於上述觀察，整個陣列要完全排序，所需的輪數就取決於 「哪一條分界線需要被跨越最多次」 。

核心轉化

總輪數 = 所有分界線中，需要向右（或向左）跨越的元素數量的最大值。
（注意：因為題目程式碼至少會執行一輪並檢查是否排序完成，所以答案至少為 1）。

對於第 ii 條分界線（前 ii 個元素與後面的元素之間）：

  • 排序前，分界線左側有 ii 個元素。
  • 排序後，這 ii 個元素中，有多少個不屬於排序後的前 ii 個位置？
  • 這些不屬於前 ii 個位置的元素，就是必須向右跨越分界線的元素。

3. 處理相同數值與穩定排序

為了精確計算每個元素「排序後的位置」，我們需要將原陣列排序。

相同數值的處理

當陣列中有相同數值時，必須保證穩定排序（Stable Sort）。也就是數值相同的元素，排序後仍保持原本的相對順序。若順序被打亂，會導致跨界數量計算錯誤。

4. 利用樹狀陣列動態統計

我們可以由左至右掃描原陣列，並維護一個資料結構來快速計算跨界數量：

  1. 掃描到第 ii 個元素時，將該元素「排序後的位置」加入資料結構。
  2. 此時，資料結構中包含了原陣列的前 ii 個元素。
  3. 查詢資料結構：這 ii 個元素中，有多少個的「排序後位置」≤i\le i？
  4. 將 ii 減去上述查詢結果，即為原本在前 ii 個位置，但排序後不在前 ii 個位置的元素數量（也就是需要向右跨越第 ii 條分界線的數量）。
資料結構選擇

由於我們需要頻繁地「單點新增」與「查詢前綴和」，樹狀陣列（Fenwick Tree / BIT） 是最理想的選擇。每次操作只需 O(log⁡N)\mathcal{O}(\log N) 時間。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)
  • 空間複雜度：O(N)\mathcal{O}(N)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class BIT:  # PURQ, 1-based
    __slots__ = ["tree"]

    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, k: int, x: int) -> None:  # 令 nums[k] += x
        while k < len(self.tree):
            self.tree[k] += x
            k += k & -k

    def preSum(self, k: int) -> int:  # 求 nums[:k+1] 之和
        res = 0
        while k > 0:
            res += self.tree[k]
            k -= k & -k
        return res


def main():
    n = int(input())
    A = [int(input()) for _ in range(n)]

    # 按照值由小到大排序，若值相同則依照原本位置排序
    # Python 的排序是穩定排序，若不是穩定排序，則使用雙關鍵字排序即可
    idxs = list(range(n))
    idxs.sort(key=lambda x: A[x])

    rank = [0] * n
    for i, idx in enumerate(idxs, start=1):
        rank[idx] = i

    bit = BIT(n)
    ans = 1
    for i, rk in enumerate(rank, start=1):
        bit.add(rk, 1)
        # 前 i 個位置中，有多少個元素最後應該去右邊
        ans = max(ans, i - bit.preSum(i))
    print(ans)


if __name__ == "__main__":
    main()