---
# System prepended metadata

title: AP325 精熟到登峰 上篇
tags: [寫精華]

---

# AP325 精熟到登峰 上篇

> 作者：沈宗叡（暴力又被TLE）

## 一、教材說明

[AP325-Python](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2Fg2kqHh5_Q4eQnz-mfNu3Kw) 是由吳邦一教授所撰寫的演算法教材，原為 C++ 版本（2020 年完成），後於 2024 年 1 月完成 Python 版本，主要針對已具備基礎程式語法知識的學習者，透過解題方式來介紹資料結構的使用與演算法思維，程度約對應 APCS 實作題從三級分到五級分的進階需求。教材包含基礎知識說明、題目講解，並附有測資供讀者練習。

而此份教材是筆者在寫完 AP325 並真的實作五級分後，又二刷並將所有題目都盡量推到最佳解法的題解，部分題目有邏輯上比 AP325 本篇更快的解法，而大部分則是著重在實作上的優化，建議在完整寫完 AP325 後再閱讀。適合對程式實作、演算法問題或者是 Python 底層機制有強烈興趣的讀者。

本文採用 [TCIRC judge](https://judge.tcirc.tw/problems/?category=3) 的題目順序撰寫，這個 Judge 對 Python 比較不友好，沒有多開時限，因此常數偏大的解可能過不了，也有些題目就算用 PyPy 仍完全不可能過得了；相較之下 [HWSH Judge](https://judge.hwsh.tc.edu.tw/Problems?tabid=apcs325#tab03) [只有一題](#021) Python 過不了，而 PyPy 可過。但後者的題目順序很亂，而且跳號問題嚴重；前者則比較輕微（但還是沒有跟講義的順序一模一樣，因此建議搭配上面的題單連結閱讀），且 Python 版本比較新，有比較多新東西可以講。總之如果在 TCIRC judge 上過不了，可以到 HWSH Judge 上試試看。

## 二、優化方法綜整

### 1. 比較 General 的優化

筆者寫的 [上一篇學習歷程](https://hackmd.io/@ericshen19555/APCS_optimized#4-優化策略概述) 裡有提到 Python 寫演算法題目的一些基本優化方法，內容大差不差。

- IO 優化

  預設的 `input` 會用 `sys.stdin.write` 先印出使用者輸入提示（就算是空字串），再使用 `sys.stdout.readline` 讀取使用者輸入，但只能一次讀一整行，並且會自動將最後的換行字元去掉，開銷頗大。

  以純 Python 表示就是：

    ```python=
    from sys import stdin, stdout

    def input(prompt: str = "") -> str:
        # 印出使用者輸入提示
        stdout.write(prompt)
        stdout.flush()
        # 讀取輸入 並去掉結尾換行\n
        return stdin.readline().rstrip("\n")
    ```

  為了更靈活、更快速的輸入，可以直接對 `sys.stdin` 執行讀檔動作，例如以下範例：
  
    ```python=
    from sys import stdin
    
    # 一次讀入一整行 保留結尾換行字元
    line: str = stdin.readline()  # 正常來講這個就夠用了

    # 讀入全部 分行存入一個 list 保留結尾換行字元
    lines: list[str] = stdin.readlines()  # 最快 但耗記憶體

    # 把 stdin 當作 iterator
    # 讀入一行
    line: str = next(stdin)  # 等價於 stdin.readline()
    # 一次讀入一行 (當遇到題目以 EOF 結尾時 這樣寫最漂亮) (但 APCS 不會有 EOF)
    for line in stdin:  # 結果上等價於 for line in stdin.readlines()
        ...

    # 一次讀入整個檔案純文字 不分行
    text: str = stdin.read()  # 基本上用不到
    # 讀入指定字數 (當輸入檔只有一行 而且大到直接輸入會 MLE) (APCS 遇不到)
    text: str = stdin.read(100)
    ```

  預設的 `print` 一樣偏慢，他接受的傳入參數很自由，並且會自動加上換行。

  以純 Python 表示就是：

    ```python=
    from sys import stdout

    def print(*objects, sep=" ", end="\n", file=None, flush=False) -> None:
        # 預設輸出到 sys.stdout
        if file is None: file = stdout
        # 將objects轉換成str 並使用sep連接 最後加上end結尾
        text: str = sep.join(map(str, objects)) + end
        # 輸出
        file.write(text)
        # 清除緩存
        if flush: file.flush()
    ```

  只需要保留其中真正用來輸出的部分就好了：
  
    ```python=
    from sys import stdout
    stdout.write(text)
    ```

  但還需要自己加上換行字元，太麻煩了。就算是多行輸出，也可以先將每行存入一個 `list[str]` 內再使用 ```"\n".join(lines)``` 組合成一個字串，然後輸出就好了。

  總之，一般我輸出還是都用 `print` 就好了，畢竟函數調用次數不多，開銷差距也就不大。

- 提升變數調用速度

  Python 中，在程式碼被編譯成字節碼後，變數調用最主要有兩種：`LOAD_NAME` 和 `LOAD_FAST`（還有其他涉及閉包或 comprehension 的，且不同版本可能不同），`LOAD_NAME` 需要在局部、全局、內建命名空間三個地方尋找這個變數，因此非常慢；而 `LOAD_FAST` 只會在局部尋找變數，因此十分快。

    ```python=
    a = 10
    print(a)  # LOAD_NAME 慢

    def f():
        a = 10
        print(a)  # LOAD_FAST 快
    ```

  為了讓變數調用的程式碼都被編譯成 `LOAD_FAST`，我們可以將所有程式碼都塞進一個函數 `main` 裡面，編譯器就知道這個變數只需要在這個函數裡面尋找就好了。

- 減少自訂函數調用

  Python 中的函數調用會創建新的 stack frame，開銷超大，尤其在大部分 Judge 的舊版本（Python 3.6）這個部分都還沒被優化過，因此非常慢。
  再加上 Python 有 $1000$ 的遞迴深度限制，超過就會直接被 `RecursionError`，雖然可以用 `sys.setrecursionlimit` 設定，最高可以到 $2^{31} - 1$，也就是 C int 的範圍，但龐大的記憶體開銷還是會讓你吃 `MLE`。

  因此基本上我都會用 Bottom-up 的邏輯來 DP，不然就用 stack 來替代遞迴，雖然實作難度直線上升，但這就是 Python 仔的宿命。只有在 backtracking 或是 merge sort 之類，遞迴深度在 20 層左右的狀況下我會使用自訂函數（就連 $1e5$ 量級的 DFS 我都一律用 stack 手刻）。

- 不要用 `try ... except` 和 `class`

  競程的實作上幾乎完全無這兩者的用武之地，他們的開銷之巨難以想像，前者應該好好用 `if` 判斷；後者用 `list` 實作即可，他不只常數較小，`__repr__` 也實作好了，debug 比較方便，完全可以取代 class 的 attribute。
  
  如果覺得用 index 當 attribute name 不好讀也難修改，可以用以下小技巧：
  
  ```python=
  class Node:
      def __init__(self, val: int, nxt: "Node"):
          self.val = val
          self.nxt = nxt
  
  node = Node(0, None)
  print(node.val)
  
  # 可以換成
  VAL, NXT = range(2)  # 以大寫命名比較不容易搞混

  node = [0, None]
  print(node[VAL])
  ```

- 快取 object 的 attributes

    如果要連續 access 一個 object 的 attribute，像是以下例子：
    
    ```python=
    def main():
        dic = {"a": 0, "b": 1, "c": 2}
        for i in input():
            print(dic.get(i))
    main()
    ```

    `dic.get` 地方就有優化的空間。分析他的字節碼，要先用 `LOAD_FAST` 找到 `dic`，再使用 `LOAD_ATTR` 在 `dic.__dict__` 裡面尋找 `get`，而 `dic.__dict__` 通常是一個哈希表，這個開銷就又開始大了。
    
    因此我們可以利用 Python 美妙的引用系統，直接拿一個變數指向 `dic.get`，這樣每次調用這個函數的時候都只需要一次 `LOAD_FAST` 就好了，快得很。

    ```python=
    def main():
        dic = {"a": 0, "b": 1, "c": 2}
        get = dic.get
        for i in input():
            print(get(i))
    main()
    ```

- 模版

    綜合以上的基本優化方法，我們可以得到一個程式模板：
  
    ```python=
    def main():  # 加速變數調用
        from sys import stdin
        e = stdin.readline  # IO加速 並快取attribute（順帶增加打字速度）
        ...
    main()
    ```

### 2. Stack 優化

- 快取最後一項
  對於一個 Stack，有用的就只有最後一項，因此我們可以將 Stack 的最後一項存入一個變數 `top`，這樣就可以避免掉 Python 超慢的 list access。
  如果在初始化時將 `top` 初始化成適當的值，像是 $\infty$ 之類的，還可以避免掉一些 edge case 的額外判斷。

- 快取函式
  Stack 常用的操作就只有 `pop`, `append`，因此我們可以用變數把他們快取起來。

- 以下是一個單調棧的簡單例子：

    ```python=
    def main():
        from sys import stdin
        e = stdin.readline

        stk = []  # 遞減單調棧
        top = float("INF")  # sentinel
        pop, append = stk.pop, stk.append  # 快取函式
        for val in map(int, e().split()):
            while top < val:
                # 需要注意去除尾端元素的邏輯
                top = pop()
            # 需要注意插入至尾端時的邏輯
            append(top)
            top = val
        ...
    main()
    ```

### 3. [分治優化](https://www.facebook.com/share/p/15eUYWW9gb/)

只要區間切得好，複雜度在 worst case 沒有爛掉，分治的理論複雜度通常不錯，但切到後面區間越來越短的時候，因為每層遞迴有較大的固定消耗，效率相對而言會越來越低。

所以區間足夠短的時候，可以用理論複雜度差一些但常數較小的演算法直接暴力解決。

除此之外，分治常常會搭配 merge sort 使用，而在大部分情況下，第一層遞迴（也就是完整的區間 $[0, n)$）是沒有必要將左右兩個區間 merge sort 的，可以省不少時間。

## 三、全題解

### [P-1-1. 合成函數(1)](https://judge.tcirc.tw/problem/d001)

基礎遞迴題，但練習使用 Stack 實作。

重點在 else case 裡面的 while 迴圈，尤其是將變數 `i` 代入公式後直接 `pop` 掉一層遞迴 Stack 的這個操作，類似於一次 `return i`。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    # f(x) = 2x - 1 ; g(x, y) = x + 2y - 3

    l = e().split()  # 輸入每個字元
    stk = []  # Stack
    top = None  # Stack 的頂端 初始化為 None 方便邊界檢查
    append, pop = stk.append, stk.pop  # 快取 Stack 常用函式
    for i in l:
        if i == "f":  # f(x)
            append(top)
            # 只有一個 parameter 不需要插空格
            top = 0  # 表示目前的函數類型為 f
        elif i == "g":  # g(x, y)
            append(top)
            append(None)  # 有兩個 parameters 需要插一個空格做暫存
            top = 1  # 表示目前的函數類型為 g
        else:
            i = int(i)  # 轉成數字 代入函數
            while top is not None:
                if top == 0:  # 前一個函數是 f
                    i = 2 * i - 1  # 直接代入公式 不需要暫存
                    top = pop()  # 將代表 f 的 1 pop 掉
                else:  # top == 1
                    x = pop()  # 檢查當前的數字是第一或二個 argument
                    if x is None:  # 現在填入的數字是第一個 argument
                        append(i)
                        break  # 沒有更多的 return 跳出迴圈
                    else:  # 現在填入的數字是第二個 argument
                        i = x + 2 * i - 3  # 將兩個數字代入公式
                        top = pop()  # 將代表 g 的 2 pop 掉
            else:  # top is None 代表整個運算式結束
                break  # 其實不用 break 程式也會自動結束 因為接下來沒有更多輸入了
    print(i)
main()
```

先補充一下 `while ... else` 這個語法，大家或許有聽過 Python 有 `for ... else` 這個語法，其實這兩者的邏輯是完全一樣的，也就是「`else` 區塊會在迴圈內沒有 `break` 的時候執行」。

舉個例子：

```python=
# for ... else
for i in range(3):
    print(i)
    if i == 2:
        print("break!")
        break
else:
    print("else!")
# 輸出: 0 1 2 break!
print(f"{i = }")  # i = 2

for i in range(3):
    print(i)
    if i == 1000:
        # Unreachable code
        print("break!")
        break
else:
    print("else!")
# 輸出: 0 1 2 else!
print(f"{i = }")  # i = 2

# while 同理
i = 0
while i < 3:
    print(i)
    if i == 2:
        print("break!")
        break
    i += 1
else:
    print("else!")
# 輸出: 0 1 2 break!
print(f"{i = }")  # i = 2

i = 0
while i < 3:
    print(i)
    if i == 1000:
        print("break!")
        break
    i += 1
else:
    print("else!")
# 輸出: 0 1 2 else!
print(f"{i = }")  # i = 3  <- 注意 while 最後一輪有多做一次 i += 1
```

### [Q-1-2. 合成函數(2)](https://judge.tcirc.tw/problem/d002)

跟上面一模一樣，主要是多了一個有三個 parameters 的 h 函數。
最大的不同在於 while 迴圈內 `top == 2` 的 case 中，判斷要填入第幾個 argument 的部分。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    # f(x) = 2x - 3 ; g(x, y) = 2x + y - 7 ; h(x, y, z) = 3x - 2y + z

    l = e().split()
    stk = []
    top = None
    append, pop = stk.append, stk.pop
    for i in l:
        if i == "f":
            append(top)
            top = 0
        elif i == "g":
            append(top)
            append(None)
            top = 1
        elif i == "h":
            append(top)
            # 三個 parameter 需要開兩格空間暫存
            append(None)
            append(None)
            top = 2
        else:
            i = int(i)
            while top is not None:
                if top == 0:
                    i = 2 * i - 3
                    top = pop()
                elif top == 1:
                    x = pop()
                    if x is None:
                        append(i)
                        break
                    else:
                        i = 2 * x + i - 7
                        top = pop()
                else:  # top == 2
                    # 先看第一個 argmunet 填了沒
                    x = stk[-2]  # (注意取值 index) (這邊沒有 pop)
                    if x is None:
                        stk[-2] = i  # 填入第一格
                        break
                    else:
                        y = pop()  # 再看第二個 argument 填了沒
                        if y is None:
                            append(i)
                            break
                        else:
                            i = 3 * x - 2 * y + i
                            pop()  # pop 掉第一個 argument (即 x)
                            top = pop()
            else:
                break
    print(i)
main()
```

### [P-1-3. 棍子中點切割](https://judge.tcirc.tw/problem/d003)

這題的 edge case 算是挺麻煩的，比較難在簡潔度和效率間權衡。
實作想法是手上一直拿著一根棍子，可以減少一些對 Stack 的 append 和 pop 操作，提升效率。
二分搜可以直接使用 `bisect.bisect_left`，[官方文件](https://docs.python.org/zh-tw/3/library/bisect.html#searching-sorted-lists) 的範例寫得超貼心，~~我忘記怎麼寫的時候都會偷翻~~。

有趣的是 APCS 檢測時是可以翻得到官方文件的，只是介面比較陽春，在 IDLE Shell 視窗打上 `help()` 或是在程式碼裡加上 `help()` 再執行都可以查詢。

示意圖：
![image](https://hackmd.io/_uploads/Hy5XWH5DJe.png)

$Time: O(n\log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left
    e = stdin.readline

    n, r = map(int, e().split())
    l = (0, *map(int, e().split()), r)  # 插入左右端點 方便取中點

    ans = 0
    stk = []
    i, j = 0, n + 1  # 正在處理的閉區間 [i, j]
    while True:
        ans += l[j] - l[i]  # 加上成本
        if i + 2 == j:  # 只有一個切點 不用繼續切
            if stk:  # 找下一根待處理的棍子
                i, j = stk.pop()
                continue
            break  # 沒棍子了 結束遞迴
        # 要找切點
        s = l[i] + l[j]
        idx = bisect_left(l, s >> 1, lo = i + 1, hi = j - 1)  # 由中點二分搜靠右切點
        # 如果 可以往左 and 左切點與中點的距離 <= 右切點與中點的距離
        if idx > i + 1 and l[idx] + l[idx - 1] >= s:
            idx -= 1  # 左側優先
        # 更新遞迴資訊
        if i + 2 <= idx:  # 如果左側棍子還能切
            if idx + 2 <= j:  # 如果右邊棍子也還能切
                stk.append((idx, j))  # 右邊棍子等等遞迴
            i, j = i, idx  # 拿左邊棍子
        else:  # 不然就拿右棍子
            i, j = idx, j
    print(ans)
main()
```

<span id="004"></span>

### [Q-1-4. 支點切割](https://judge.tcirc.tw/problem/d004)

我的 [前一篇學習歷程](https://hackmd.io/UtqevkNyQDeXzkCzuLemdw?view#55-%E9%82%8F%E8%BC%AF%E5%84%AA%E5%8C%96:~:text=1\)%0A%E2%80%8Bmain()-,f638%20%E6%94%AF%E9%BB%9E%E5%88%87%E5%89%B2,-%E5%8F%83%E8%80%83%E8%A7%A3%E9%A1%8C%E5%A0%B1%E5%91%8A) 也有收錄這題 APCS 考古題。

參考解題報告: [找支點O(1)的方法](https://zerojudge.tw/ShowThread?postid=30025&reply=0)

此題限制切割層級 $K<30$，因此使用遞迴可以 AC，但還是練習用 Stack。

這題一般來講就是用 sliding window 的邏輯，線性複雜度找切點；但也可以藉由億些前綴和寫出區間力矩和的 $O(1)$ 查值（常數稍大），再對區間內二分搜就能 $O(\log_2 n)$ 找切點；然而這遠沒有直接套質心公式來得好寫又快速，而套公式需要注意的就是各種 edge case，選的切點不能在邊緣、小數如何四捨五入...等等。

[`itertools.accumulate`](https://docs.python.org/zh-tw/3/library/itertools.html#itertools.accumulate) 跟 C++ 的 `std::accumulate` 作用不一樣，C++ 的更接近 Python 的 [`functools.reduce`](https://docs.python.org/zh-tw/3.13/library/functools.html#functools.reduce)。
簡單來講，預設的情況下就是對傳入的 `iterable` 做出前綴和的表（第 15 行），回傳的是一個 `iterator`，當然也可以指定特殊的運算函數，像是 `accumulate(it, mul)` 就會做出階乘表。
而 `initial` 則是 Python 3.8 才加入的新功能，就等價於把這一項加到傳入的 `iterable` 的第一項，但 APCS 內用不了。

[`itertools.starmap`](https://docs.python.org/zh-tw/3/library/itertools.html#itertools.starmap) 其實就是一般的 `map`，只是加上了一個 `*` 用於引數傳入函數時的 unpacking，也就是說在對 `iterable` 的每一項 parameter 傳入時，`map` 是 `function(a, b)`；而 `starmap` 則是 `function(*c)`，結果論而言是 `map(func, iterable1, itertable2)` 等價於 `starmap(func, zip(iterable1, itertable2))`。當然，`zip` 起來再丟給 `starmap` 做 unpacking 是脫褲子放屁，我從來只會將 `starmap` 跟 `enumerate` 搭配使用。

`int.__mul__` 是取整數用於相乘的函式，`int.__mul__(a, b)` 等價於 `a.__mul__(b)` 也等價於 `a * b`（要把前兩個的差別解釋清楚就得提到 class 和 OOD，好個大坑！還是請讀者自己跟 ChatGPT 求教吧！），更 pythonic 的寫法是用 `operation.mul`，但 import 會有性能損耗，所以我通常直接拿 magic method。

$Time: O(n+2^k), Space: O(n+2^k)$

```python=
def main():
    from sys import stdin
    from itertools import accumulate, starmap
    e = stdin.readline

    """
    質心公式: (x 表示位置, m表示質量)
    sum(xi * mi for xi, mi in zip(x, m)) / sum(m)
    """

    n, k = map(int, e().split())
    l = tuple(map(int, e().split()))
    # 求質心需要用到區間和 把前綴和準備好 (1-based)
    # >= Python 3.8 accumulate(initial=)
    p = tuple(accumulate(l, initial=0))
    xp = tuple(accumulate(starmap(int.__mul__, enumerate(l)), initial=0))
    # < Python 3.8
    # p = (0, *accumulate(l))
    # xp = (0, *accumulate(starmap(int.__mul__, enumerate(l))))

    ans = 0
    # 初始化 區間為整個棍子(左閉右開) 切割層級1
    stk = [(0, n, 1)]
    append, pop = stk.append, stk.pop
    while stk:
        # 取出一個區間
        i, j, d = pop()

        # 計算切點
        sxp, sp = xp[j] - xp[i], p[j] - p[i]  # 前綴和取區間 (1-based)
        q, r = divmod(sxp, sp)
        if r > sp >> 1:  # 四捨五入選靠近實際切點的位置 (>而不是>= 因為左側優先)
            q += 1

        # 不能切邊邊 校正回歸
        if q <= i:
            q = i + 1
        elif q >= j - 1:
            q = j - 2

        # 更新答案
        ans += l[q]

        # 分割新的區間
        if d < k:  # 確保切割層級
            # 左半邊
            t = q - i  # 該區間長度
            if t == 3:  # 長度剛好為3 可以直接更新答案
                ans += l[i + 1]
            elif t > 3:  # >3 就存起來等等切
                append((i, q, d + 1))
            # <3 不能切 直接丟掉

            # 右半邊 同理
            t = j - q - 1
            if t == 3:
                ans += l[q + 2]
            elif t > 3:
                append((q + 1, j, d + 1))
    print(ans)
main()
```

### [Q-1-5. 二維黑白影像編碼](https://judge.tcirc.tw/problem/d005)

我的 [前一篇學習歷程](https://hackmd.io/UtqevkNyQDeXzkCzuLemdw?view#54-%E5%84%AA%E5%8C%96stack-%E9%81%BF%E5%85%8D%E9%81%9E%E8%BF%B4:~:text=n%22\)%0A%E2%80%8Bmain()-,f637%20DF%2Dexpression,-%E9%A1%8C%E7%9B%AE%E7%B5%A6%E7%9A%84) 也有收錄這題 APCS 考古題。

題目給的 $n \le 1024$，前面就有提到使用函式遞迴的話很有可能會吃 `RecursionError`，而且函式遞迴的常數很大，而此題各層遞迴之間的變數傳遞關係很單純，因此繼續練習 Stack 的寫法。

一般寫法可能是紀錄邊長，紀錄答案時再平方，而我的寫法是直接紀錄面積，層級變化時再 `*4` 或 `/4` (位元運算左右移兩位)；Stack 中紀錄的是當前區塊還剩多少子區塊尚未處理，並使用 `cur` 變數快取 Stack 的最後一項。

`stk` 初始化時放的 `None` 可以是任何值，只是為了在全部遞迴結束後，最後一次 `pop()` 時不會 `IndexError: pop from empty list`，當然也可以將 `cur` 初始化為 `2`，但這樣誤導性有點強。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    s = e().strip()
    area = int(e()) ** 2

    ans = 0
    stk = [None]  # None 是為了在全部遞迴結束後 最後一次 pop() 不會 IndexError
    cur = 1  # 初始化為一大塊
    append, pop = stk.append, stk.pop  # 快取函數
    for i in s:
        # 處理目前這塊
        cur -= 1
        if i != "2":  # i == "0" or "1"
            # 加上黑色面積
            if i == "1": ans += area
            # 將已經處理完的色塊pop掉 把面積*4
            while cur == 0:
                cur = pop()
                area <<= 2
        else:  # i == "2"
            # 面積/4 分成四小塊
            area >>= 2
            append(cur)
            cur = 4
    print(ans)
main()
```

<span id="006"></span>

### [P-1-7. 子集合乘積](https://judge.tcirc.tw/problem/d006)

這題會用到費馬小定理，需要算 $a$ 的模逆元 $a^{p - 2} \mod p$，因此會需要用到快速冪，Python 內建的 [`pow(base, exp, mod)`](https://docs.python.org/zh-tw/3.13/library/functions.html#pow) 本身就支援快速冪，不需要手刻，直接用就好了，但如果要比賽還是要會，矩陣快速冪是很基礎的考點。
有趣的是在 Python 3.8 以後，只要 `exp` 填負數就會變成計算模逆元，可以少做一些大數減法（對 Python 來說很有差），但 APCS 還是不能用（雖然 APCS 也不會考快速冪和費馬小定理）。

接下來講講 [`collections.defaultdict`](https://docs.python.org/zh-tw/3/library/collections.html#defaultdict-objects)，`defaultdict` 是 `dict` 的子類，也就是說他繼承了 `dict` 的所有功能，唯一有區別的就是 `__missing__` 這個函式（雖然他在 C 裡沒有實際被實作成一個獨立的 magic method），最主要影響到的就是 `__getitem__` 這個 method，也就是 `val = dic[key]`，當 `key` 不存在的時候一般的 `dict` 會報 `KeyError`，而 `defaultdict` 則是會在 `key` 不存在時創建一個預設值，這個預設值從哪來？這就是 `defaultdict(default_factory)` 在初始化（準確來說是實例化）時傳入的 `default_factory` 的用處，這個預設值就是 `default_factory()`，為何要傳入函數而不是直接傳入值？因為如果直接傳入值，之後每個 `__missing__` 創建的 `key` 都會指向這個 object，就亂套了，類似 `[[]] * n` 這個初學者容易犯的小錯誤。
注意到，`defaultdict` 只有 override `__getitem__` 這個 method，也就是說 `get` 不受影響，`get` 在遇到不存在的值的時候還是預設會回傳 `None` 且不建立任何新鍵值對，下面的例子就是用這個特性節省時間。

幾個 `defaultdict` 常常搭配的 `default_factory`：
```python=
from collections import defaultdict

# 常用
defaultdict(int)  # 0  用來替代 Counter
defaultdict(list) # [] 鄰接串列存圖

# 偶爾
defaultdict(set)  # set()
defaultdict(dict) # {}

# 冷門
defaultdict(bool) # False

# 字典樹
nested_dict = lambda: defaultdict(nested_dict)
trie = nested_dict()
```

其實還有另一個專門用來計數的 [`collections.Counter`](https://docs.python.org/zh-tw/3/library/collections.html#collections.Counter)，功能超級多超好用，但缺點是超級肥超級慢，一般來講用不到這麼多功能，因此我都用 `defaultdict(int)` 更快一些。

Python 3.8 還加入了 [`:=` 海象運算子](https://docs.python.org/zh-tw/3.13/reference/expressions.html#assignment-expressions)，就是更自由的變數賦值，在以下例子裡也成就了一定的性能提升，既避免了 `val` 不存在時，比較需要注意的是他的運算優先級非常低，要記得括號，還有記得 APCS 不能用。

最後查值的部分還有一個小巧思：遍歷 `sa` 對 `sb` 查值，因為在 `n` 是奇數的時候，`sa` 會比 `sb` 小一半，而 `dict` 的查值又是 $O(1)$，因此遍歷小的效率更高。

$Time: O(2^{n / 2}\log_2p) \space Space: O(2^{n/2})$

```python=
def main():
    from sys import stdin
    from itertools import islice
    from collections import defaultdict
    e = stdin.readline
    p = 10009

    n = int(e())
    l = map(int, e().split())

    # 折半枚舉
    sa, sb = defaultdict(int), defaultdict(int)
    sa[1] = sb[1] = 1  # 方便建表 後面會扣掉
    for i in islice(l, n >> 1):  # 取前半部
        for k, v in tuple(sa.items()):
            sa[k * i % p] += v
    for i in l:  # 取剩下的
        for k, v in tuple(sb.items()):
            sb[k * i % p] += v

    # 配對 sa sb 並扣掉一個1*1的對
    # >= Python 3.8 pow(a, -1, p), :=
    print(sum(v * u for k, v in sa.items()
              if (u := sb.get(pow(k, -1, p))) is not None) - 1)
    # < Python 3.8
    # print(sum(v * sb[pow(k, p-2, p)] for k, v in sa.items()) - 1)
main()
```

<span id="007"></span>

### [Q-1-8. 子集合的和](https://judge.tcirc.tw/problem/d007)

我就直接放最佳解了。

這種題型有兩種可能，第一種：$a_i$ 很小，就是經典的背包，如果不帶權可以直接用一個 `int` 用來表示一個 `list[bool]`，Python 的大數位元運算雖然超級慢，但也比列表操作快上一個量級，而最後要求的答案通常跟 lowbit `x & -x` 有關，lowbit 就是指一個二進位數字裡面最右側的一個 $1$，舉個例子，`0b10010000` 的 lowbit 就是 `0b10000`，lowbit 的性質很不錯，是後面會提到的 Binary Indexed Tree 用到的重要性值；第二種：$a_i$ 超大，$n$ 則在 $30$ 上下，那就是折半枚舉，也就是這題的解法。

先看看第一種解法會怎麼做：

$Time: O(n \times p), Space: O(p)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    n, p = map(int, e().split())
    a = map(int, e().split())

    bit = 1
    mask = (1 << p + 1) - 1
    for i in a:
        bit |= bit << i
        bit &= mask
    print(bit.bit_length() - 1)
main()
```

在 TLE 前就 MLE 了。

第二種解法：

為了節省建表時間和記憶體，把其中一個數字先拿出來，在後面查表的時候再順便算，`sb` 就可以少複製一遍。

枚舉的部分，為了不要重複加到同一輪枚舉的數字，使用 [`itertools.islice`](https://docs.python.org/zh-tw/3.13/library/itertools.html#itertools.islice) 限制枚舉的範圍，`islice(it)` 大概像是 `list[slice()]` 的概念，最主要的區別是 `islice` 輸入是 `iterable`，不一定需要能 random access，而回傳的是 iterator；`list[slice()]` 則是回傳一個全新的 `list`，在 `list` 很大的時候就會燒雞，也是初學者常常犯的錯誤之一，但很小的時候卻又會有亮眼的表現，所以 Python 枚舉題的壓常是玄學，我也不會。

這一次因為第一項被拿走，所以變成 $n$ 是偶數的時候 `sb` 會是 `sa` 的一半，因此排序和二分搜都是對 `sb` 做，可以讓 $\log$ 項比較小（但也就小了 $1$？）。

$Time: O(n \times 2^{n/2}), Space: O(2^{n/2})$

```python=
def main():
    from sys import stdin, stdout
    from bisect import bisect_right
    from itertools import islice
    e = stdin.readline

    n, p = map(int, e().split())
    l = map(int, e().split())
    x = next(l)  # 第一項最後計算的時候再加入

    ans = 0
    sa, sb = [0], [0]
    for u in islice(l, n >> 1):
        for v in islice(sa, len(sa)):
            v += u
            if v <= p:
                sa.append(v)
    for u in l:
        for v in islice(sb, len(sb)):
            v += u
            if v <= p:
                sb.append(v)
    sb.sort()
    mx = sb[-1]

    for v in sa:
        if ans - mx < v:  # 簡易減枝 減少二分搜次數
            # 嘗試未加第一項
            k = bisect_right(sb, p - v) - 1
            ans = max(ans, v + sb[k])
        v += x
        if ans - mx < v <= p:  # 簡易減枝 減少二分搜次數
            # 加上第一項
            k = bisect_right(sb, p - v) - 1
            ans = max(ans, v + sb[k])
    stdout.write(str(ans))  # 上 IO 加速才好過 d019
main()
```

另一種用 [`itertools.combinations`](https://docs.python.org/zh-tw/3.13/library/itertools.html#itertools.combinations) 枚舉的方法，有 C 的黑魔法加持再加上惰性的生成，空間複雜度只有 $O(n)$，十分省記憶體（上面的解的一半），效率意外地也不錯。
[`itertools.chain.from_iterable`](https://docs.python.org/zh-tw/3.13/library/itertools.html#itertools.chain.from_iterable) 則是用來將一個 `iterable[iterable]` 裡面的一個個 `iterable` 展開，連接在一起變成一長串。

```python=
def main():
    from sys import stdin, stdout
    from bisect import bisect_right
    from itertools import islice, chain, combinations
    e = stdin.readline

    n, p = map(int, e().split())
    l = map(int, e().split())
    x = next(l)  # 第一項最後計算的時候再加入

    # 枚舉前半部
    it = tuple(islice(l, n >> 1))
    r = len(it) + 1
    # 對每種挑選數量生成子集合 就是 C(n, 1) + C(n, 2) + ... + C(n, n) 的概念
    sa = sorted(v for v in map(sum, chain.from_iterable(combinations(it, i)
                                        for i in range(1, r))) if v <= p)
    ub, mx = p - sa[0], sa[-1]

    ans = 0
    it = tuple(l)
    r = len(it) + 1
    # 惰性枚舉 省記憶體
    for v in map(sum, chain.from_iterable(combinations(it, i)
                                          for i in range(1, r))):
        if ans - mx < v <= ub:
            # 嘗試未加第一項
            k = bisect_right(sa, p - v) - 1
            ans = max(ans, v + sa[k])
        v += x
        if ans - mx < v <= ub:
            # 加上第一項
            k = bisect_right(sa, p - v) - 1
            ans = max(ans, v + sa[k])
    stdout.write(str(ans))  # 得上 IO 加速才過得了 d019
main()
```

### [Q-1-10. 最多得分的皇后](https://judge.tcirc.tw/problem/d008)

這題原本在舊的中一中 Judge 上面我不管怎麼寫都 TLE（或許是我那時候還太菜 QwQ），後來在[社團上發問](https://www.facebook.com/share/p/19HUUuxZjs/)後，可以說是我第一次寫了一個「真正的剪枝」，也就是 `ub` 的部分，我是將每一行各取最大值總加，每一列同理，然後兩個方向取值比較小的當上界，如果加上這個理想值還是無法更新答案，就不需要繼續 DFS 下去了。

很多人可能都不知道 `enumerate` 還有第二個 `parameter`，預設值是 `0`，簡單來說就是從多少開始數。下面的例子也可以寫成 `enumerate(tmp, 1)` 就好了，但這個東西有點冷門，我還是會加上 `start=` 增加可讀性。

`nonlocal` 和 `global` 的差別也是個很重要的坑，[這個影片](https://youtu.be/tLcDQhy9Ew0)講得非常好。

```python=
def main():
    from sys import stdin
    e = stdin.readline

    def backtracking(l, i=0, cur=0):
        nonlocal best  # 要對外層變數賦值需要用 nonlocal 宣告
        best = max(best, cur)  # 更新答案
        if i == n: return  # 到底了 backtracking
        # 計算 upper_bound 用於剪枝
        ub = min(sum(max(i) for i in l), 
                 sum(max(i) for i in zip(*l)))
        if cur + ub <= best: return  # 不可能更新答案 剪枝
        # 先嘗試跳過這行
        backtracking([i.copy() for i in l[1:]], i + 1, cur)
        for j in range(n):  # 窮舉每個位置
            v = l[0][j]
            if v == 0: continue  # 放不了
            # 放下去 把攻擊範圍內的格子刪掉
            tmp = [i.copy() for i in l[1:]]  # 複製一份
            for idx, row in enumerate(tmp, start=1):
                row[j] = 0
                if j + idx < n:
                    row[j + idx] = 0
                if j - idx >= 0:
                    row[j - idx] = 0
            backtracking(tmp, i + 1, cur + v)

    n = int(e())
    l = [list(map(int, e().split())) for i in range(n)]

    best = 0
    backtracking(l)
    print(best)
main()
```

WIP：DLX解

### [Q-1-11. 刪除矩形邊界](https://judge.tcirc.tw/problem/d009)

我就直接放最佳解了。

Bottom-up DP，四維稍微麻煩一點但也還好，index 填對了就沒什麼問題。加上前綴和，快速算成本。

$Time: O(m^2n^2), Space: O(m^2n^2)$

```python=
def main():
    from sys import stdin
    from itertools import accumulate
    e = stdin.readline

    m, n = map(int, e().split())
    area = m * n
    l = tuple(map(tuple, (map(int, e().split()) for _ in range(m))))

    # >= Python 3.8 accumulate(initial)
    pr = tuple(tuple(accumulate(row, initial=0)) for row in l)
    pc = tuple(tuple(accumulate(col, initial=0)) for col in zip(*l))
    # < Python 3.8
    # pr = tuple((0, *accumulate(row)) for row in l)
    # pc = tuple((0, *accumulate(col)) for col in zip(*l))

    # dp[t][s][j][i] = 將 [s, t) [i, j) 這個矩陣刪除的最小花費
    dp = [[[[0] * j for j in range(n + 1)] for _ in range(i)] for i in range(m + 1)]

    # bottom-up
    # 所有大小為1的矩陣成本為0 初始化後就不用dp 所以矩陣大小 r, c 都從2開始
    for r in range(2, m + 1):
        for s in range(m - r + 1):
            t = s + r
            chunk = dp[t][s]
            for c in range(2, n + 1):
                for i in range(n - c + 1):
                    j = i + c

                    # 欲求最小花費 初始化為整個圖的面積(無限大的意思)
                    res = area

                    # 以四個方向收縮為前置狀態 加上刪除的花費
                    x = pc[i][t] - pc[i][s]
                    x = min(x, r - x)  # 和翻轉後的取小
                    res = min(res, chunk[j][i + 1] + x)

                    x = pc[j - 1][t] - pc[j - 1][s]
                    x = min(x, r - x)
                    res = min(res, chunk[j - 1][i] + x)

                    x = pr[s][j] - pr[s][i]
                    x = min(x, c - x)
                    res = min(res, dp[t][s + 1][j][i] + x)

                    x = pr[t - 1][j] - pr[t - 1][i]
                    x = min(x, c - x)
                    res = min(res, dp[t - 1][s][j][i] + x)

                    chunk[j][i] = res
    print(dp[m][0][n][0])
main()
```

### [P-2-1. 不同的數—排序](https://judge.tcirc.tw/problem/d010)

Python 的內建排序演算法是所有語言裡面最好的，沒有之一。
大部分人可能都還認為 Python 的排序演算法是 Tim Sort，但在 Python 3.11 之後 Python 的內建排序法就被 Power Sort 取代了，因為 Tim Sort 在極端狀況下可能會在分治時將區間切成一個很大一個很小，導致合併時效率很差，而 Power Sort 就是改善了這個問題的 Tim Sort，名字中的 "Power" 就是取自他切區間的方式，好像是用 $2$ 的次方去算出甚麼 magic number，再用他來切區間，但我實在找不到談論詳細細節的介紹。

$Time: O(n\log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline
    e()
    l = sorted(set(map(int, e().split())))  # 去重並排序
    print(len(l))
    print(*l)
main()
```

### [P-2-2. 離散化 – sort](https://judge.tcirc.tw/problem/d011)

沒什麼好聊了...

$Time: O(n\log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline
    e()
    l = tuple(map(int, e().split()))
    k = {v: i for i, v in enumerate(sorted(set(l)))}.__getitem__
    print(*map(k, l))
main()
```

### [P-2-3. 快速冪](https://judge.tcirc.tw/problem/d012)

別急，等等就會手刻快速冪了。

$Time: O(\log_2 n), Space: O(1)$

```python=
print(pow(*map(int, input().split())))
```

### [Q-2-4. 快速冪--200 位整數](https://judge.tcirc.tw/problem/d013)

Python 的大數雖然慢到爆，但用起來還是挺爽的。
沒錯，程式碼跟上一題一模一樣。

$Time: O(\log_2 n), Space: O(1)$

```python=
print(pow(*map(int, input().split())))
```

### [Q-2-5. 快速計算費式數列第 n 項](https://judge.tcirc.tw/problem/d014)

因為是以 $-1$ 結尾而不處理，不想寫 if 判斷這個 case，所以就 iterate 下一項，處理這一項，用這個邏輯就不會計算到最後一項了，只會把他讀進來。

矩陣乘法的部分因為對稱，所以只有三項，直接寫死。
真要寫我會寫這個：

```python=
def matmul(a, b):
    return tuple(
        tuple(sum(map(mul, row, col)) % mod
              for col in zip(*b))
        for row in a
    )
```

$Time: O(t\log_2 n), Space: O(1)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    def fab(n):
        if n < 3: return int(n > 0)  # 前三項直接特判
        n -= 2  # 轉移次數
        d = p = (1, 1, 0)
        while n:
            if n & 1:
                p = matmul(p, d)
            d = matmul(d, d)
            n >>= 1
        return p[0]

    def matmul(a, b):
        x = (a[0] * b[0] + a[1] * b[1]) % p
        y = (a[0] * b[1] + a[1] * b[2]) % p
        z = (a[1] * b[1] + a[2] * b[2]) % p
        return (x, y, z)

    p = 1000000007
    it = map(int, stdin)
    n = next(it)
    for nxt in it:
        print(fab(n))
        n = nxt
main()
```

### [P-2-6. Two-Number problem](https://judge.tcirc.tw/problem/d015)

挑小的做成 `set` 以增加效率。

$Time: O(m + n), Space: O(\min(m, n))$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    m, n, k = map(int, e().split())
    a = map(int, e().split())
    b = map(int, e().split())
    if m > n: a, b = b, a
    a = set(a)

    print(sum(1 for i in b if k - i in a))
main()
```

### [Q-2-7. 互補團隊](https://judge.tcirc.tw/problem/d016)

考點是如何有效率地表示集合並快速找出補集，二進位就是一個很好的集合表示方式，常數小效率高。

比較怪異的是將字母轉換成 bit 的方法，用 `1 << ord(c) - 65` 反而會比用一個 `dict` 建表再查表慢，主要是因為前者用了比較多 Python 層面的操作（而且大數的位元操作很慢），而後者則全部是 C 層面的操作，乾淨俐落。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    # 將大寫字母對應到每個的 bit
    get = {'A': 1, 'B': 2, 'C': 4, 'D': 8, 'E': 16, 'F': 32, 'G': 64, 
           'H': 128, 'I': 256, 'J': 512, 'K': 1024, 'L': 2048, 'M': 4096, 
           'N': 8192, 'O': 16384, 'P': 32768, 'Q': 65536, 'R': 131072, 
           'S': 262144, 'T': 524288, 'U': 1048576, 'V': 2097152, 'W': 4194304, 
           'X': 8388608, 'Y': 16777216, 'Z': 33554432}.__getitem__

    m, n = map(int, stdin.readline().split())
    s = set()  # 哪些子集合有出現
    add = s.add  # 快取函數
    for it in map(str.rstrip, stdin):  # 每行輸入並去掉結尾換行
        # 將字母集合轉換成一個二進位數字表示的集合
        bit = 0
        for i in map(get, it):  # 將大寫字母 轉換成二進位 bit
            bit |= i
        add(bit)

    every = (1 << m) - 1  # 總共有哪些人
    # 對每個子集合查詢其補集是否存在 答案為 互補組數/2 -1
    print(sum(1 for i in s if (every & ~i) in s) >> 1)
main()
```

### [Q-2-8. 模逆元](https://judge.tcirc.tw/problem/d017)

裸題，直接費馬小定理。

$Time: O(n\log_2p), Space: O(1)$

```python=
p = int(input().split()[1])  # n 用不到
# >= Python 3.8 pow(exp < 0)
print(*(pow(i, -1, p) for i in map(int, input().split())))
# < Python 3.8
# print(*(pow(i, p-2, p) for i in map(int, input().split())))
```

### [P-2-9. 子集合乘積](https://judge.tcirc.tw/problem/d018)

約等於 [P-1-7. 子集合乘積](#006)，但這題 $n$ 比較大，可以少枚舉一個數字，最後查表時再考慮。

$n$ 為偶數時，`sb` 會是 `sa` 的一半，因此遍歷 `sb` 對 `sa` 查表。

$Time: O(2^{n / 2}\log_2p) \space Space: O(2^{n/2})$

模逆元直接用 Python 3.8 以後的寫法。

```python=
def main():
    from sys import stdin
    from collections import defaultdict
    from itertools import islice
    e = stdin.readline

    n, p = map(int, e().split())
    l = map(int, e().split())
    x = next(l)  # 第一項最後計算的時候再加入

    sa, sb = defaultdict(int), defaultdict(int)
    sa[1] = sb[1] = 1  # 便於建枚舉表
    for u in islice(l, n >> 1):
        # 使用 tuple() 複製一份字典 才不會重複乘到同一個數字
        for v, c in tuple(sa.items()):
            sa[u * v % p] += c
    for u in l:
        # 使用 tuple() 複製一份字典 才不會重複乘到同一個數字
        for v, c in tuple(sb.items()):
            sb[u * v % p] += c

    ans = 0
    get = sa.get  # 快取函式
    for v, c in sb.items():
        ans += c * (
            get(pow(v, -1, p), 0) +
            get(pow(v * x, -1, p), 0)
        )
    print((ans - 1) % p)  # 扣掉 1 * 1 的 case
main()
```

### [Q-2-10. 子集合的和](https://judge.tcirc.tw/problem/d019)

題解完全同 [Q-1-8. 子集合的和](#007)。

### [P-2-11. 最接近的區間和](https://judge.tcirc.tw/problem/d020)

Python 沒有內建 Red Black Tree，僅有的 `sortedcontainers.SortedList` 也僅僅是第三方套件，我所知的範圍內只有 LeetCode 裡面有裝，還是少數沒有事先 import 的套件。沒有內建的有序容器是 Python 除了效能以外的另一大劣勢。

第一種方法是用 `bisect.insort` 硬插，時間複雜度 $O(n)$，但有 C 的黑魔法加持，常數很小，如果測資沒有特別針對的話過得了（甚至很快）。

$Time: O(n^2), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left, insort
    from itertools import accumulate
    e = stdin.readline

    n, k = map(int, e().split())
    # 儲存所有前綴和
    s = [0]  # 初始化為 [0] 讓第一輪的 s[-1] 不報錯
    ans = 0
    for v in accumulate(map(int, e().split())):  # 做前綴和
        # 對所有前綴和二分搜 找出配對起來最接近而不超過 k 的
        if v - s[-1] <= k:  # 篩掉必定超過 k 的 case (s[idx] 會 Index Error)
            idx = bisect_left(s, v - k)
            ans = max(ans, v - s[idx])
        insort(s, v)  # 插入前綴和 維護升冪 O(n)
    print(ans)
main()
```

第二種方法是手刻一個陽春的 `sortedcontainers.SortedList`，~~因為直接把原始碼整個貼上去會被 Judge 嗆~~，Python 的 `SortedList` 不是使用 RBT，而是用二維分塊的邏輯，將 $1000$ 量級的列表操作視為常數，當一個塊的長度超過 $2000$ 的時候，就將其均分成兩塊，實作上這個操作由 `_expand` 函數負責；當一個塊的長度小於 $500$ 的時候，就與前或後的塊合併，再對合併的塊執行 `_expand`。
這題因為只有插入操作，所以只需要刻 `_expand` 就好了。

`SortedList` 原始碼：

```python=
def _expand(self, pos):
    """Split sublists with length greater than double the load-factor.

    Updates the index when the sublist length is less than double the load
    level. This requires incrementing the nodes in a traversal from the
    leaf node to the root. For an example traversal see
    ``SortedList._loc``.

    """
    _load = self._load  # 理想區間長度 預設1000
    _lists = self._lists  # 儲存所有塊
    _index = self._index  # 用以支援 index 取值的線段樹

    if len(_lists[pos]) > (_load << 1):  # 超過限制 分成兩塊
        _maxes = self._maxes  # 用以快取每塊最大值(即每塊最後一項)

        _lists_pos = _lists[pos]  # 要切的塊
        half = _lists_pos[_load:]  # 複製右半塊
        del _lists_pos[_load:]  # 刪除右半塊
        _maxes[pos] = _lists_pos[-1]  # 更新左半塊的最大值

        _lists.insert(pos + 1, half)  # 將右半塊插入
        _maxes.insert(pos + 1, half[-1])  # 插入右半塊最大值

        del _index[:]  # index 線段樹需要砍掉重種
    else:
        if _index:  # 如果線段樹在可維護狀態的話就更新他
            child = self._offset + pos
            while child:
                _index[child] += 1
                child = (child - 1) >> 1
            _index[0] += 1
```

以 $\sqrt n$ 作為理想分塊長度。

$Time: O(n \sqrt n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left, insort
    from itertools import accumulate
    e = stdin.readline

    n, k = map(int, e().split())
    load = int(n ** 0.5)  # 取 isqrt(n) 為門檻值
    lists = [[0]]  # 儲存所有塊
    maxes = [0]  # 快取每塊最大值 用於第一層二分搜
    ans = 0
    for v in accumulate(map(int, e().split())):  # 做前綴和
        # 對所有前綴和二分搜 找出配對起來最接近而不超過 k 的
        if v - maxes[-1] <= k:  # 篩掉必定超過 k 的 case
            t = v - k  # 二分搜目標值
            i = bisect_left(maxes, t)  # 第一層二分搜 鎖定塊
            chunk = lists[i]
            j = bisect_left(chunk, t)  # 第二層二分搜 鎖定目標
            ans = max(ans, v - chunk[j])  # 更新答案

        # 插入前綴和 維護升冪
        if v >= maxes[-1]:
            if v == maxes[-1]: continue  # 剛好跟目前最大值一樣 跳過
            i = len(maxes) - 1  # 加到最後一個塊尾端
            block = lists[-1]
            block.append(v)
            maxes[-1] = v  # 更新最後一個塊的最大值
        else:
            i = bisect_left(maxes, v)  # 第一層二分搜 鎖定塊
            block = lists[i]
            insort(block, v)  # 第二層二分搜 插入值

        # _expand
        if len(block) >= (load << 1):  # 太長 要切塊
            half = block[load:]  # 取右半塊
            del block[load:]  # 刪掉右半塊
            maxes[i] = block[-1]  # 更新左半塊最大值
            lists.insert(i + 1, half)  # 插入右半塊
            maxes.insert(i + 1, half[-1])  # 插入右半塊最大值
    print(ans)
main()
```

還有另一種方法不會用到資結，而且複雜度是漂亮的 $O(n\log_2 n)$，那就是分治，最一開始是在寫 [下一題](#021) 的時候不管怎樣都被 TLE，[求助](https://www.facebook.com/groups/359446638362710/posts/1274119463562085/?comment_id=1274166743557357) 於吳邦一教授後他提點的解法：

> 這題當初是為了 C++ 設計的，原測資大小的話，Python 即使用了 SortedList 都過不了。我在 Python 版有把測資放小一點。如果 SortedList 不能用的話，可以用 divide and conquer 代替，**跨過中線的解把兩邊的 prefix sum 與 suffix sum 分別排序，用二分搜或者雙指標爬行**，時間 $O(M^2N\log^2N)$。

我最後想出的做法則是先對整個數列做前綴和，跨過中線的解用雙指標配對左右端點，再右減左得出區間。

實作上可以善用 Python 的 iterator，熟練後可以更輕鬆地撰寫這種雙指標的麻煩邏輯（好不好寫比較算個人偏好），並使用 `for` 和 `next(iterator, None)` 漂亮地應對 `StopIteration`，跑起來比 `list[idx]` 還要快。
需要注意的是 merge 的時候，因為都要先從 iterator 內預取一個數字出來比較，最後在左右串列其中一個結束、另一個還剩的時候，可別忘了把這個預取的數字 merge 進去。

那個 `for ... while ... else ... else` 的迴圈可能比較難理解，我標上了各個流程控制指令會跳到哪一行，可以多多琢磨一下。

```python=
def main():
    from sys import stdin
    from itertools import accumulate
    e = stdin.readline

    # 分治 [s, t) 時間 O(nlogn)
    def merge(s, t):  # -> list[int]
        nonlocal ans  # 宣告取得上一層的變數
        # 結束條件: 區間長度 == 1
        if s + 1 == t: return [l[s]]

        # 切一半 分治
        mid = s + t >> 1
        le = merge(s, mid)
        ri = merge(mid, t)

        # 雙指標處理跨中線的區間
        it = iter(le)
        u = next(it)
        for v in ri:  # 對於每個右端點
            # 找到相減區間 <= k 的左端點
            while (val := v - u) > k:
                u = next(it, None)
                if u is None: break  # 左端點沒了
            else:
                # 更新答案
                if val > ans: ans = val
                continue
            break  # 左端點沒了就結束配對

        # 將區間和 merge sort
        res = []
        le, ri = iter(le), iter(ri)
        u = next(le)
        for v in ri:
            while u <= v:
                res.append(u)
                u = next(le, None)
                if u is None:  # left end
                    res.append(v)  # 記得加這項
                    res.extend(ri)
                    break  # -> 51
            else:  # left not end
                res.append(v)
                continue  # -> 41 ... 53
            break  # left end -> 56
        else:  # left not end
            res.append(u)  # 記得加這項
            res.extend(le)

        return res

    n, k = map(int, e().split())
    # 做前綴和
    # >= Python 3.8 accumulate(initial=)
    l = tuple(accumulate(map(int, e().split()), initial=0))
    # < Python 3.8
    # l = (0, *accumulate(map(int, e().split())))
    ans = 0
    merge(0, n + 1)  # 分治 [0, n + 1)
    print(ans)
main()
```

<span id="021"></span>

### [Q-2-12. 最接近的子矩陣和](https://judge.tcirc.tw/problem/d021)

為了過這題我可是煞費苦心。

標準解法是對 $m$ 方向做前綴和，再窮舉任兩行相減，變成一個個直向區間和，再對這一列由區間和形成的數列求「最接近的子區間和」，時間複雜度 $O(m^2n\log_2 n)$。
但這一算起來，大概有 $5.6e7$ 的計算量，Python 得跑幾十秒（可不是十幾秒）。

在「觀察」了測資（把每個測資的 $m, n$ 偷出來）以後，發現主要只有兩種極端測資：$(1, 3e6)$ 和 $(50, 6000)$，因此我們就針對這兩種大小的測資做優化，當然如果有甚麼 $(10, 3e5)$ 之類的測資的話就是融合這兩種極端的解法再去細調。

對於 $(1, 3e6)$，就是「最接近的子區間和」，只是將結束條件改成用常數小的 $O(n)$ 解法暴力求長度 $5000$ 以內的區間。

對於 $(50, 6000)$，因為總共有 $\binom{50}{2} = 1225$ 個數列要做「最接近的子區間和」，實在太多了！因此我們可以設法篩選掉一些：如果當前數列的「最大子區間和」比目前得到的「最接近的子區間和」還要小，那就代表這個數列不可能更新答案，可以跳過。
而分治——尤其是 merge sort 的部分——受限於 Python 的列表操作速度而超級無敵慢，為了不 merge sort，我們乾脆只分治一層，也就是只切成左右區間，個別 $O(n^2)$ 暴力算，再雙指標處理跨中線的區間，如果左右的前綴和形成的最大區間比目前的「最接近的子區間和」還要小，那就代表任一組跨中線的區間不可能更新答案，或是如果左右的前綴和形成的最小區間比 $k$ 還要大，就代表任一組跨中線的區間都不合，可以跳過。
如果好奇如果不切兩塊，而是切成三塊、四塊，再枚舉所有左右配對的情況做雙指標，一樣不用 merge sort，會不會比較快？我測過，不會，主要是因為雙指標計算的部分有太多純 Python 操作，很慢。

總之，結果 Python 還是過不了，PyPy 則能打敗部分 C++ 的正常解。

$Time: \begin{cases}
O(n \log_2 n), & \text{if } m = 1, \\
O(m^2 n^2), & \text{otherwise.}
\end{cases}, Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left, insort
    from itertools import accumulate, combinations, islice
    e = stdin.readline
    add, sub = int.__add__, int.__sub__  # 快取加減法函數

    k = int(e())
    m, n = map(int, e().split())

    if m == 1:  # 矩陣退化為一行 n可以很大 用分治比較穩定
        # 將區間分治處理
        def merge(s, t):  # -> list[int]
            nonlocal ans
            # 區間長度 <= 5000 時直接暴力求 O(n²)
            if t - s <= 5000:
                it = islice(l, t - s)  # 限制取的區間
                # 第一項特殊處理
                mx = next(it)
                res = [mx]
                if ans < mx <= k:
                    ans = mx
                # 繼續處理後面的
                for p in it:
                    if p - mx <= k:
                        idx = bisect_left(res, p - k)
                        ans = max(ans, p - res[idx])
                    insort(res, p)
                    if p > mx: mx = p
                return res

            # 切一半 分治
            mid = s + t >> 1
            le = merge(s, mid)
            ri = merge(mid, t)

            # 雙指標處理跨中線的區間
            it = iter(le)
            u = next(it)
            for v in ri:  # 對於每個右端點
                # 找到相減區間 <= k 的左端點
                while (val := v - u) > k:
                    u = next(it, None)
                    if u is None: break  # 左端點沒了
                else:
                    # 更新答案
                    if val > ans: ans = val
                    continue
                break  # 左端點沒了就結束配對

            # 第一層遞迴不用merge sort
            if s == 0 and t > n: return

            # 將區間和 merge sort
            res = []
            le, ri = iter(le), iter(ri)
            u = next(le)
            for v in ri:
                while u <= v:
                    res.append(u)
                    u = next(le, None)
                    if u is None:  # left end
                        res.append(v)  # 記得加這項
                        res.extend(ri)
                        break
                else:  # left not end
                    res.append(v)
                    continue
                break  # left end
            else:  # left not end
                res.append(u)  # 記得加這項
                res.extend(le)

            return res

        ans = 0
        # >= Python 3.8 accumulate(initial)
        l = accumulate(map(int, e().split()), initial=0)
        # < Python 3.8 用 chain 代替
        # l = chain((0, ), accumulate(map(int, e().split())))
        merge(0, n + 1)

    else:
        p = (0,) * n
        grid = [p]
        for i in range(m):  # 將每一直列做前綴和
            p = tuple(map(add, p, map(int, e().split())))
            grid.append(p)

        ans = 0
        for a, b in combinations(grid, 2):  # 選取前綴和兩行
            # map(sub, b, a): 相減變成區間

            # 先做一次最大連續區間和 如果 <= ans 就剪枝
            dp = res = 0
            for v in map(sub, b, a):
                # 卡丹算法
                dp += v
                if dp > res: res = dp
                elif dp < 0: dp = 0
                if res > ans: break  # 可能更新答案
            else: continue  # 不可能更新答案 剪枝

            it = accumulate(map(sub, b, a))

            # 左右各自 O(n²) 暴力求
            mx = 0
            le = [0]
            for v in islice(it, n >> 1):
                if v - mx <= k:
                    idx = bisect_left(le, v - k)
                    ans = max(ans, v - le[idx])
                insort(le, v)
                if v > mx: mx = v

            mx = 0
            ri = [0]
            for v in it:
                if v - mx <= k:
                    idx = bisect_left(ri, v - k)
                    ans = max(ans, v - ri[idx])
                insort(ri, v)
                if v > mx: mx = v

            # 最大區間和比當前答案還小 或 最小區間和超過 k 就剪枝
            if ri[-1] - le[0] <= ans or ri[0] - le[-1] > k:
                continue

            # 雙指標處理跨中線的區間
            le = iter(le)
            u = next(le)
            for v in ri:
                while v - u > k:
                    u = next(le, None)
                    if u is None: break  # 左端點沒了
                else:
                    v -= u  # 相減成區間
                    if v > ans: ans = v  # 更新答案
                    continue  # 繼續雙指標枚舉
                break  # 左端點沒了就跳出

            # 只有分治一層 不用 merge sort

    print(ans)
main()
```

### [Q-2-13. 無理數的快速冪](https://judge.tcirc.tw/problem/d022)

上一題好恐怖，來個簡單的快速冪壓壓驚。
這題的特色就是無理數乘法而已。

$Time: O(\log_2 n), Space: O(1)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    p = 1000000009
    i, j, n = map(int, e().split())
    n -= 1  # 次方: 1 -> n, 轉移 n - 1 次
    x, y = i, j
    while n > 0:
        if n & 1 == 1:
            i, j = (i * x + 2 * j * y) % p, (i * y + j * x) % p
        x, y = (x * x + 2 * y * y) % p, (x * y << 1) % p
        n >>= 1
    print(i, j)
main()
```

### [Q-2-14. 水槽](https://judge.tcirc.tw/problem/d023)

這題把雙指標耍得十分精妙。

這題實作上的小細節主要在找隔板的部分，一樣是用 iterator 以減少 `list` 取值操作，也減少實作難度。

[`operator.itemgetter(idx)`](https://docs.python.org/zh-tw/3.13/library/operator.html#operator.itemgetter) 就是創建一個專門取 `idx` 這個索引取值函式，等價於 `lambda obj: obj[idx]`，最常與 `sort`, `bisect` 和 `groupby` 搭配使用。

差分序列 `ans` 只維護 $n - 1$ 格的資料，而多開一格可以在區間修改時少寫 edge case 判斷，只是最後還原時要記得把最後一格刪掉。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from itertools import accumulate
    from operator import itemgetter
    e = stdin.readline

    n, x, w = map(int, e().split())
    # 按照高度降冪排列 保留index
    # 做成iterator後取其next函式
    nxt = iter(sorted(enumerate(map(int, e().split())),
                      key=itemgetter(1), reverse=True)).__next__

    ans = [0] * n # 差分序列 方便區間修改
    s, t = 0, n - 1 # 維護一個還沒填水的區間 (為左右擋板的index)
    while True:
        if s == t - 1: # 單格水直接放
            ans[s] += w
            ans[t] -= w
            break

        # 找到此區間內最高的隔板
        i, h = nxt()  # index, height
        while not s < i < t:
            i, h = nxt()

        # 剩餘水量 > 整個區間加到最大隔板高度的體積
        # 整個區間平均分配剩餘水量
        l = t - s
        if w > h * l:
            h = w // l
            ans[s] += h
            ans[t] -= h
            break

        # 看水量是否越過擋板
        # 沒有越過就縮小區間
        # 有越過就把當前區間填滿 並移到空區間繼續填
        if x < i: # 注水於左側
            v = h * (i - s)
            if w <= v: # 水不會越過
                t = i  # 將區間收斂於左側
            else: # 水會越過(到右邊) 區間修改左側
                ans[s] += h
                ans[i] -= h
                w -= v # 水變少
                s = i  # 接著看右側區間
        else: # x >= i 注水於右側
            v = h * (t - i)
            if w <= v: # 水不會越過
                s = i  # 將區間收斂於右側
            else: # 水會越過(到左邊) 區間修改右側
                ans[i] += h
                ans[t] -= h
                w -= v # 水變少
                t = i  # 接著看左側區間

    # 將差分還原
    ans.pop()  # 去掉結尾的 sentinel
    print(*accumulate(ans))
main()
```

<span id="024"></span>

### [P-2-15. 圓環出口](https://judge.tcirc.tw/problem/d024)

環狀數列題最簡單的應對方式就是把數列複製，接到後面，這樣就能無痛解決頭尾的問題。

而以下是不用此技巧，踏踏實實判斷 edge case 的解法。

這個解漂亮的部分在於建立前綴和的時候，最前面多加了一個 $0$，而使數列變成 1-based，讓「完成任務後停在下一個房間」這件事情變得十分自然，但最後別忘了要 `% n`。

$Time: O(n \log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left
    from itertools import accumulate
    e = stdin.readline

    n, m = map(int, e().split())
    # 做成前綴和
    # >= Python 3.8 accumulate(initial)
    p = tuple(accumulate(map(int, e().split()), initial=0))
    # < Python 3.8
    # p = (0, *accumulate(map(int, e().split())))
    last = p[-1]  # 快取前綴和最後一項

    idx = 0
    for i in map(int, e().split()):
        # 試試看走到底夠不夠
        rest = last - p[idx]
        if rest == i:
            # 剛剛好
            idx = 0
        else:
            if rest < i:
                # 走到底還不夠 要繞回頭
                # 那就先走到底再二分搜
                i -= rest
                idx = 0
            idx = bisect_left(p, p[idx] + i)
    print(0 if idx == n else idx)  # idx % n 的意思
main()
```

### [P-3-1. 樹的高度與根](https://judge.tcirc.tw/problem/d025)

基本圖論題。

直覺想法：首先找出根節點，只要看誰不是任何人的子節點就好了。接下來從根 DFS 下去，當前節點的高度就是最高的子節點 +1。

```python=
# 找根節點
isroot = [True] * n
for children in tree:  # 假設 tree 紀錄每個節點的所有子節點
    for node in children:
        isroot[node] = False
root = isroot.index(True)

# DFS
def dfs(node: int) -> int:  # 回傳當前節點高度
    return max((dfs(child) + 1 for child in tree[node]), default=0)
dfs(root)  # 就可以找出根節點的高
```

這樣的複雜度無疑是好的，時間空間都是 $O(n)$，但別忘了我們在寫 Python，`dfs()` 的遞迴深度會是樹的深度，最差的情況就是樹是一條直鏈，深度可以達到 $1e5$ 量級，遠遠超過 $1000$ 的深度限制，當然也可以用 Stack 手刻遞迴，但不好寫，那何不換個方向？從上往下麻煩，就由下往上唄！

大方向是「每一輪處理所有高度相同的節點」，子節點數量是 $0$ 的就是葉子，也是遍歷的第一層，而遍歷一個節點前必須先遍歷其所有的子節點，下面這棵樹的遍歷順序就是 $[4, 5, 6], [2, 3], [1], [0]$。可以發現這樣的遍歷方式有很好的性質：第 $i$ 輪遍歷到的節點之高度就是 $i - 1$，而且最後一層只會有根節點，這樣問題就整個解決了！

![image](https://hackmd.io/_uploads/BJfuXu0P1e.png)

如何實作？將輸入改成紀錄每個節點的父節點，方便由下往上溯源，並紀錄每個節點的度數 `indeg`，每次遍歷到一個節點就將其父節點的 `indeg` 減少，當父節點的 `indeg` 為 $0$ 就代表他所有的子節點都遍歷過了，需要加入下一輪遍歷。

一般的 BFS 實作為了避免 `list.pop(0)` 這種燒雞寫法主要有兩種方式：使用 `collections.deque` 雙向佇列的 `deque.popleft`，他的複雜度是 $O(1)$；或者直接不從左邊移除元素，單純用一個指標指向當前遍歷到的地方，雖然感覺空間會燒雞，但仔細一想時間空間都是 $O(n)$，因此不會有問題，但總歸是浪費了空間。
以下這種 BFS 則是我很喜歡的一種實作方式（而且是原創），在兩種解法中間取了個折衷，避免了連續進行 `pop` 這種常數大的列表操作，又不會保留所有已經遍歷完的節點，最讚的是他可以同時維護當前的遍歷層數。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    pa = [None] * n
    indeg = [0] * n
    cur = []  # bfs由葉子開始
    for i in range(n):
        child = map(int, e().split())
        indeg[i] = cn = next(child)
        if cn == 0:  # 子節點數為零就是葉子
            cur.append(i)
        else:
            for j in child:  # 讓每個子節點都找得到爸爸
                pa[j - 1] = i

    ans = height = 0
    while cur:
        nxt = []
        ans += height * len(cur)  # 計算當層高度總和
        for i in cur:
            p = pa[i]
            if p is None:  # 到根就停
                break
            # bfs擴散
            indeg[p] -= 1
            if indeg[p] == 0:
                nxt.append(p)
        cur = nxt
        height += 1
    print(i + 1)  # 最後一個掃到的就是根 轉成1-based
    print(ans)  # 節點高度總和
main()
```

### [P-3-2. 括弧配對](https://judge.tcirc.tw/problem/d026)

括弧九成以上都是 Stack 題，這題如果只有一種括弧的話可以將 Stack 簡化為計數，達到常數空間，但有三種括弧的話就沒辦法了。

實作小技巧是將六種字元分別對應到一個數字，同時使左括號的編號 +3 後就是對應的右括號編號，這樣一來判斷就好做了！其中將 `\n` 也編號，並在 Stack 初始化時放個對應的數字，這樣就不用將輸入字串 `str.rstrip`，省下一些時間。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin, stdout
    ans = []
    trans = "([{)]}\n".index  # 將括號轉換成對應編號的函式
    for s in stdin:  # 每行輸入 保留結尾換行
        stk = [6]  # sentinel 與\n配對
        for c in map(trans, s):  # 逐字轉換成編號
            if c < 3:  # 左括號
                stk.append(c + 3)
            elif stk.pop() != c:  # 右括號
                # 配對不上
                ans.append("no")
                break
        else:
            # 全部配對完才是合法
            ans.append("yes" if len(stk) <= 1 else "no")
    stdout.write("\n".join(ans))
main()
```

### [Q-3-3. 加減乘除](https://judge.tcirc.tw/problem/d027)

再次體會到 Python 的美妙之處。
需要注意的是 Python 的預設除法是真除法，依題意需要替換成整數除法。

$Time: O(n), Space: O(n)$

```python=
print(eval(input().replace("/", "//")))
```

好，認真來寫寫。
題目限制所有數字都是一位正整數，只會有加減乘除，不會有括號，那根本不用用到 Stack。

將 `+`, `-` 分隔的一個個只含乘除法的子字串稱為區塊，易知每個區塊之間不會互相影響，因此可以直接累加，而將每個區塊的結果初始化為 $1$ 的話，就只有遇到 `/` 的時候需要做除法，因為遇到 `+`, `-` 的時候必定剛初始化完，會是 $1 \times ...$ 的形式。

實作上有一點需要特別注意：為何不要根據當前是 `+`, `-` 來初始化 `cur` 為 $1$, $-1$ 就好了，還能少用一個變數 `sub`？確實可以，但 `//` 除法是向下取整，就要改成向 $0$ 取整才行，最簡單的改法是將 `cur //= c` 改成 `cur = int(cur / c)`，就是有點醜。

實作勇士可以來挑戰我出的 [暴力又被TLE 想讓人滅台](https://hackmd.io/dUgOKVDmR_aSp68oXUQDxw)，可以到 [APCSS Judge](https://apcs-simulation.com/problem/apcs1703_py) 上測試。

$Time: O(n), Space: O(1)$

```python=
def main():
    from sys import stdin
    ans, cur = 0, 1  # 加總後的答案, 目前在處理的小區塊
    sub = div = False  # 前一個+-是不是-, 前一個+-*/是不是/
    for c in stdin.readline():  # 保留換行字元
        if c.isdigit():  # 是數字
            c = int(c)
            if div:  # 只有/需要做除法
                cur //= c
            else:  # 因為cur初始化為1 不管*+-都直接*就好
                cur *= c
        else:  # 是運算子
            if c in "+-\n":  # 進到一個新的區塊 結算前一區塊
                if sub:  # 前一個區塊做的是減法
                    ans -= cur
                else:  # 前一個區塊做的是加法
                    ans += cur
                sub = (c == "-")
                cur = 1  # 初始化為 1 方便運算
            div = (c == "/")  # 接下來是否做除法
    print(ans)
main()
```

### [P-3-4. 最接近的高人](https://judge.tcirc.tw/problem/d028)

設好 sentinel，套上一些 Stack 優化。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    l = map(int, e().split())

    ans = 0
    stk = []
    append, pop = stk.append, stk.pop
    ph, pi = float("INF"), -1  # 不可能超越的sentinel 位置-1
    for i, v in enumerate(l):
        # 維護身高的單調對列
        while ph <= v:
            ph, pi = pop()
        ans += i - pi  # 更新答案
        append((ph, pi))
        ph, pi = v, i
    print(ans)
main()
```

### [Q-3-5. 帶著板凳排雞排的高人](https://judge.tcirc.tw/problem/d029)

就是上一題加上二分搜。

為了要能使用 `bisect`，我們要讓原本遞減的單調棧變成遞增，加上負號就好了，可以利用 `tuple` 的比較特性，把高度放在前面一欄。

當然另一種方式是分成兩個 `list`，一個存高度、一個存位置，因為 `tuple` 的比較速度慢，所以這是效率最高的方式；或是用 Python 3.10 後 `bisect` 加入的 `key`，但自訂函數比 tuple 比較還慢。

為了二分搜，不能將頂端元素另外快取。

$Time: O(n \log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_right
    e = stdin.readline

    n = int(e())
    l = zip(map(int, e().split()), map(int, e().split()))

    ans = 0
    # 身高取負號 遞增才能用bisect
    stk = [(float("-INF"), -1)]  # 不可能超越的sentinel 位置-1
    for i, (v, x) in enumerate(l):
        # 板凳加上身高 拿去二分搜
        idx = bisect_right(stk, (-x-v, )) - 1
        ans += i - stk[idx][1] - 1

        # 維護身高的單調對列
        while stk[-1][0] >= -v:
            stk.pop()
        stk.append((-v, i))
    print(ans)
main()
```

<span id="030"></span>

### [P-3-6. 砍樹](https://judge.tcirc.tw/problem/d030)

我的 [前一篇學習歷程](https://hackmd.io/UtqevkNyQDeXzkCzuLemdw?view#54-%E5%84%AA%E5%8C%96stack-%E9%81%BF%E5%85%8D%E9%81%9E%E8%BF%B4:~:text=%E7%9A%84%E5%84%AA%E5%8C%96%E3%80%82-,h028%20%E7%A0%8D%E6%A8%B9,-%E9%80%99%E9%A1%8C%E6%AF%94%E8%BC%83) 也有收錄這題 APCS 考古題。

這題比較明顯是純 Stack的題目。

比較有意思的是我 one-pass 的方式，輸入的資訊都維持 iterator 的狀態，遍歷時遍歷要砍的樹 `cur` 的右邊那棵樹 `nxt`，以 `nxt` 和前面未砍的樹 `last` （即為 `stack[-1]`）的位置判斷 `cur` 是否能往左右砍倒。

左側邊界條件，也就是 Stack 內的樹全都被砍空的情況，我在 `stack[0]` （也就是初始化時的last）放了一顆無限高的樹，因此他跟吳剛的桂樹一樣不可能被砍倒；右側邊界條件，則是用 `itertools.chain` 在輸入的最後安插了一顆位置 `R` 高度 `None` 的樹（使用None是因為其進行大部分運算時皆會報錯，便於 debug），因為只會討論 `nxt` 的前一棵樹是否能砍，右邊界 `(R, None)` 時沒有更右邊的樹了，因此程式不會考慮這顆「樹」。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from itertools import chain
    e = stdin.readline

    n, R = map(int, e().split())
    p = map(int, e().split())
    h = map(int, e().split())

    c = m = 0  # 可砍數量 最大高度
    # 初始化stack
    stk = []  # 儲存暫時沒辦法砍的樹的stack
    extend, pop = stk.extend, stk.pop  # 快取函數
    lp, lh = 0, float("INF")  # 快取stack的最後一項 初始化為 sentinel
    # 製作所有樹的iterator
    it = chain(zip(p, h), ((R, None), ))  # 加入右邊界
    cp, ch = next(it)  # 目前這棵樹 初始化先取第一項
    for np, nh in it:  # 取下一顆樹 討論目前這棵樹(cp, ch)能否被砍
        # 往右砍 或 往左砍
        if ch <= np - cp or ch <= cp - lp:
            # 可以直接砍掉
            c += 1
            m = max(ch, m)

            # 看前面的樹能不能往右砍
            while lh <= np - lp:
                c += 1
                m = max(lh, m)
                lh, lp = pop(), pop()
        else:
            # 往左往右都壓到 沒辦法砍 先加到stack
            extend((lp, lh))
            lp, lh = cp, ch
        cp, ch = np, nh
    print(c, m, sep="\n")
main()
```

### [P-3-7. 正整數序列之最接近的區間和](https://judge.tcirc.tw/problem/d031)

[`itertools.tee`](https://docs.python.org/zh-tw/3/library/itertools.html#itertools.tee) 是個特別有意思的函數，`iterator` 的特色就是遍歷過的東西直接丟掉，而 `tee` 則是提供了複製 `iterator` 的功能，複製出來的 $n$ 個 `iterator` 會共用傳入的那個 `iterator`，利用 linked-list 的概念（在 Python 3.11 以前似乎是用一個 queue 來維護？），暫存跑得最快和最慢的 `iterator` 之間的值，如果所有 `iterator` 都已經將某個值讀取完，這個值就會失去引用並被自然地回收掉。
這題因為維護的區間長度不固定，最長可能到 $n$，所以空間複雜度是 $O(n)$。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from itertools import tee
    e = stdin.readline

    n, k = map(int, e().split())
    # 將iterator複製
    l, p = tee(map(int, e().split()), 2)
    nxt = p.__next__  # 快取 左區間的取值函式
    u = nxt()  # 取左邊第一項

    ans = cnt = cur = 0
    for i, v in enumerate(l):
        cur += v  # 向右擴展區間
        while cur > k:  # 太大 縮減左側區間
            cur -= u
            u = nxt()
        # 更新最大值
        if cur > ans:
            ans = cur
            cnt = 1
        elif cur == ans:
            cnt += 1
    print(ans, cnt, sep="\n")
main()
```

### [P-3-8. 固定長度區間的最大區段差](https://judge.tcirc.tw/problem/d032)

固定區間長度 $k$，`itertools.tee` 能使空間複雜度降到 $O(k)$。

[`collections.deque`](https://docs.python.org/zh-tw/3.13/library/collections.html#collections.deque) 是用 doubly-linked-list 實作的，因此兩端的操作非常快。一般對 `list` 右端的操作加個 `left` 尾綴就會是 `deque` 的左端操作，像是 `popleft`, `appendleft`, `extendleft` 等等，比較特殊的是 `rotate` 函數，會將整個 `deque` 進行輪轉，`deque.rotate(1)` 等價於 `deque.appendleft(deque.pop())`，負數則反之。

$Time: O(n), Space: O(k)$

```python=
def main():
    from sys import stdin
    from collections import deque  # 使用deque雙向隊列 方便把第一項移除
    from itertools import islice, tee
    e = stdin.readline

    n, k = map(int, e().split())
    l, p = tee(map(int, e().split()), 2)

    # 先取第一個區間
    M, m = deque(maxlen=k), deque(maxlen=k)
    for i in islice(l, k):
        # 維護嚴格遞減/遞增
        while M and M[-1] < i: M.pop()
        while m and m[-1] > i: m.pop()
        M.append(i)
        m.append(i)
    M0, m0 = M[0], m[0]
    ans = M0 - m0

    for i, j in zip(l, p):
        # 先處理被丟掉的首項
        if j == M0: M.popleft()  # 首項是最大值
        if j == m0: m.popleft()  # 首項是最小值

        # 處理最後加入的一項 跟取第一個區間時一樣
        while M and M[-1] < i: M.pop()
        while m and m[-1] > i: m.pop()
        M.append(i)
        m.append(i)

        # 更新答案
        M0, m0 = M[0], m[0]
        ans = max(ans, M0 - m0)
    print(ans)
main()
```

### [P-3-9. 最多色彩帶](https://judge.tcirc.tw/problem/d033)

使用一個變數 `cur` 維護當前色彩種類數，看當前增加、減少的顏色其數量是否在 $0, 1$ 之間切換。

$Time: O(n), Space: O(k)$

```python=
def main():
    from sys import stdin
    from itertools import islice, tee
    e = stdin.readline

    n, k = map(int, e().split())
    l, p = tee(map(int, e().split()), 2)

    c = {}
    cur = 0
    # 先取第一個區間
    for i in islice(l, k):
        v = c.get(i, 0)
        c[i] = v + 1
        if v == 0:
            cur += 1
    ans = cur

    for i, j in zip(l, p):
        # 先處理被丟掉的首項
        v = c.get(j, 0)
        c[j] = v - 1
        if v == 1:
            cur -= 1

        # 更新此項
        v = c.get(i, 0)
        c[i] = v + 1
        if v == 0:
            cur += 1

        # 更新答案
        if cur > ans: ans = cur
    print(ans)
main()
```

### [P-3-10. 全彩彩帶](https://judge.tcirc.tw/problem/d034)

這題要求全彩，因此可以先將包含所有顏色的計數器字典建立好，也節省後續存取的時間。

為了減少記憶體使用也同時增加效率，將區間長度維護在「當前的答案」以下且不全彩的狀態，如果當前區間是全彩就嘗試縮減左側。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    ans = int(e())
    l = tuple(map(int, e().split()))

    c = dict.fromkeys(l, 0)  # 建立所有顏色的計數器
    k = len(c)  # 全彩顏色數
    l, p = iter(l), iter(l)
    nxt = p.__next__

    # 目前區間長度, 區間內顏色種類數
    s = t = 0
    for i in l:
        # 維護區間長度 <= ans
        if s == ans:
            # 移除左端點
            j = nxt()
            v = c[j]
            c[j] -= 1
            if v == 1:
                t -= 1
        else:
            s += 1

        # 新增右端點
        v = c[i]
        c[i] += 1
        if v == 0: t += 1

        # 達到全彩
        if t == k:
            # 嘗試收斂左側區間 直到不再全彩
            while True:
                # 移除左端點
                s -= 1
                j = nxt()
                v = c[j]
                c[j] -= 1
                if v == 1:
                    t -= 1
                    break  # 不再全彩
            # 目前的區間(長度s)不全彩
            # 但加上剛移除的最後一個左端點就能全彩
            # 所以 s + 1 全彩
            if s < ans:
                ans = s + 1
    print(ans)
main()
```

### [Q-3-11. 最長的相異色彩帶](https://judge.tcirc.tw/problem/d035)

維護一個異色區間，遇到區間內已經有的顏色就縮減區間直到左端點遇到該顏色。

$Time: O(n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from itertools import tee
    e = stdin.readline

    n = int(e())
    l, p = tee(map(int, e().split()), 2)
    nxt = p.__next__

    s = set()
    ans = cur = 0
    for i in l:
        if i in s:  # 同色
            while True:  # 移除左端點
                j = nxt()
                if j == i:  # 跟即將加入的右端點的同色
                    break  # 不用移除 直接跳出
                s.remove(j)
                cur -= 1
        else:  # 異色 需要加入
            s.add(i)
            cur += 1

        # 更新答案
        if cur > ans: ans = cur
    print(ans)
main()
```

### [Q-3-12. 完美彩帶](https://judge.tcirc.tw/problem/d036)

有兩種想法：維護長度為 $k$ 的區間，檢查顏色種類是否為 $k$；或者反過來維護一個盡可能長的異色區間，看顏色種類（即區間長度）是否為 $k$。

第一種方式：
$Time: O(n), Space: O(k)$

```python=
def main():
    from sys import stdin
    from itertools import islice, tee
    e = stdin.readline

    k, n = map(int, e().split())
    l, p = tee(map(int, e().split()), 2)

    c = {}
    cur = 0
    # 先取第一個區間
    for i in islice(l, k):
        v = c.get(i, 0)
        c[i] = v + 1
        if v == 0:
            cur += 1
    ans = 1 if cur == k else 0

    for i, j in zip(l, p):
        # 先處理被丟掉的首項
        v = c.get(j, 0)
        c[j] = v - 1
        if v == 1:
            cur -= 1

        # 更新此項
        v = c.get(i, 0)
        c[i] = v + 1
        if v == 0:
            cur += 1

        # 更新答案
        if cur == k: ans += 1
    print(ans)
main()
```

第二種方式：
$Time: O(n), Space: O(k)$

```python=
def main():
    from sys import stdin
    from itertools import tee
    e = stdin.readline

    k, n = map(int, e().split())
    l, p = tee(map(int, e().split()), 2)
    nxt = p.__next__

    s = set()
    ans = cur = 0
    for i in l:
        if i in s:  # 同色
            while True:  # 移除左端點
                j = nxt()
                if j == i:  # 跟即將加入的右端點的同色
                    break  # 不用移除 直接跳出
                s.remove(j)
                cur -= 1
        else:  # 異色 需要加入
            s.add(i)
            cur += 1

        # 更新答案
        if cur == k: ans += 1
    print(ans)
main()
```

### [Q-3-13. X差值範圍內的最大Y差值](https://judge.tcirc.tw/problem/d037)

先照 $x$ 排序，維護 $\Delta x \le k$ 的區間，用兩個單調雙向對列紀錄當前 $\Delta y$。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from collections import deque
    e = stdin.readline

    n, k = map(int, e().split())
    # 對x座標做排序
    l = sorted(zip(map(int, e().split()), map(int, e().split())))
    # 左端點iterator
    p = iter(l)
    nxt = p.__next__
    px, py = nxt()

    ans = 0
    M = deque() # y最大值單調隊列
    m = deque() # y最小值單調隊列
    for x, y in l:
        # 維護兩個單調隊列
        while M and M[-1] < y: M.pop()
        while m and m[-1] > y: m.pop()
        M.append(y)
        m.append(y)

        # 移除左邊的點 保持x區間在k以內
        while M and x - px > k:
            if M[0] == py: M.popleft()
            if m[0] == py: m.popleft()
            px, py = nxt()

        # 更新答案
        ans = max(ans, M[0] - m[0])
    print(ans)
main()
```

### [Q-3-14. 線性函數](https://judge.tcirc.tw/problem/d038)

使用 Stack 維護斜率的單調性，Stack 最後狀態即為 `F(x)`。

最後讀取 Stack 的邏輯很漂亮，預取下一條線的交點，並用無限遠的交點避免觸發邊界條件。與 [P-3-6. 砍樹](#030) 的那顆吳剛的無限高桂樹有著異曲同工之妙。

$Time: O(\text{sort} + n + m), Space: O(n + m)$

```python=
def main():
    from sys import stdin
    e = stdin.readline
    lm = float("-INF")  # left most

    n, m = map(int, e().split())
    # 排列: 斜率升冪 y截距降冪
    l = iter(sorted((tuple(map(int, e().split())) for i in range(n)), 
                    key=lambda x: (x[0], -x[1])))

    # 取第一項
    px = lm
    pa, pb = next(l)
    stk = []
    for a, b in l:
        # 斜率與前一相同 y截距較小 用不到
        if a == pa: continue
        # 找出被新線覆蓋掉的舊線 丟掉
        while True:
            # 求新線與最後一條舊線交點之x (沒被卡精度)
            x = (b - pb) / (pa - a)
            # 檢查覆蓋情形
            if x <= px:
                # 覆蓋掉
                px, pa, pb = stk.pop()
            else:
                # 沒覆蓋掉 跳出
                break
        # 新增新線
        stk.append((px, pa, pb))
        px, pa, pb = x, a, b
    # 新增最後一條新線 & 右界sentinel
    stk.extend(((px, pa, pb), (float("INF"), None, None)))

    ans = 0
    it = iter(stk)
    _, a, b = next(it)
    nx, na, nb = next(it)
    for c in sorted(map(int, e().split())):
        while c >= nx:  # 找到此x座標所屬的最大值之線
            a, b = na, nb
            nx, na, nb = next(it)
        ans += c * a + b  # x代入函數求解
    print(ans)
main()
```

### [P-4-1. 少林寺的代幣](https://judge.tcirc.tw/problem/d042)

基本的貪心。

來講講 `divmod` 函式（在 [Q-1-4. 支點切割](#004) 的程式碼中就有使用到），`divmod(a, b)` 就等價於 `(a // b, a % b)`，但少做一次除法，就醬。

$Time: O(t), Space: O(1)$

```python=
def main():
    from sys import stdin
    stdin.readline()  # 測資數量 用不到

    l = (50, 10, 5)  # 兌換代幣 由大到小
    for x in map(int, stdin):  # 每行輸入轉成 int
        ans = 0
        for i in l:  # 貪心地兌換
            q, x = divmod(x, i)
            ans += q
        print(ans + x)  # 加上兌換為 1 元的
main()
```

### [P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/problem/d043)

基本的貪心。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    e()  # 人數 用不到
    # 貪心地升冪排序
    a = iter(sorted(map(int, e().split())))
    b = sorted(map(int, e().split()))
    j = next(a)  # 預取一項 用於比較

    ans = 0
    for i in b:
        if i > j:
            # 如果每場都贏 最後會 StopIteration
            j = next(a, None)  # None 不會被比較到
            ans += 1
    print(ans)
main()
```

### [P-4-3. 十年磨一劍](https://judge.tcirc.tw/problem/d044)

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from itertools import accumulate
    e = stdin.readline

    e()  # 劍數 用不到
    # 升冪排序後 前綴和總和
    print(sum(accumulate(sorted(map(int, e().split())))))
main()
```

### [P-4-4. 幾場華山論劍](https://judge.tcirc.tw/problem/d045)

`itemgetter(1)` 等價於 `lambda x: x[1]` 但更快。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    n = int(e())
    # 按照結束時間排序
    l = sorted((tuple(map(int, e().split())) for i in range(n)), 
               key=itemgetter(1))

    ans = 0
    end = -1  # 結束時間初始化為 -1 第一場活動必取
    for s, t in l:
        if s > end:  # 貪心地參加
            end = t  # 更新結束時間
            ans += 1  # 場次+1
    print(ans)
main()
```

### [P-4-5. 嵩山磨劍坊的問題](https://judge.tcirc.tw/problem/d046)

可以先用 [`filter`](https://docs.python.org/zh-tw/3.13/library/functions.html#filter) 去掉權重為 $0$ 的訂單，`filter(function, iterable)` 等價於 `(i for i in iterable if function(i))`，但因為很少有適合的 `function` 而需要使用 `lambda`，因此我通常會寫後者，這題剛好只需要把 $0$ 去掉，而 `bool(int)` 等價於 `int != 0`，因此只需要用 `itemgetter` 取 `tuple` 的第二個即可。順帶一提 `filter(None, iterable)` 等價於 `(i for i in iterable if i)`。

而後面 `key=lambda x: x[0] / x[1]` 的部分我真的想不到甚麼好的函式可以達成一樣的功能，`operator.truediv` 等價於 `lambda a, b: a / b`，跟所需差了一次 unpacking，而 Python 也沒有內建將 function 加上一次 unpacking 的 decorator，只有 `starmap` 這樣特定的例子。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    e()
    # 依照 時間/權重 由小排到大 (權重為0直接刪除)
    l = sorted(filter(itemgetter(1), 
                      zip(map(int, e().split()), map(int, e().split()))), 
               key=lambda x: x[0] / x[1])

    ans = now = 0
    for t, w in l:
        now += t  # 累加時間
        ans += now * w  # 乘上權重
    print(ans)
main()
```

### [Q-4-6. 少林寺的自動寄物櫃](https://judge.tcirc.tw/problem/d047)

和上一題只差在累加時間和計算權重的順序。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    e()
    # 依照時間/權重由小排到大 (權重為0直接刪除)
    l = sorted(filter(itemgetter(1), 
                      zip(map(int, e().split()), map(int, e().split()))), 
               key=lambda x: x[0] / x[1])

    ans = now = 0
    for t, w in l:  # 與上一題的差別是下面兩行調換
        ans += now * w
        now += t
    print(ans)
main()
```

### [P-4-7. 岳不群的併派問題](https://judge.tcirc.tw/problem/d048)

[`heapq`](https://docs.python.org/zh-tw/3.13/library/heapq.html) 是少數有純 Python 程式碼的內建函式庫（`bisect` 也有，只是他的實作很簡單），如果用 `dir(heapq)` 看一下會發現除了 `heapq.__all__` 裡面列出來的 `heappush`, `heappop`, `heapify`, `heapreplace`, `merge`, `nlargest`, `nsmallest`, `heappushpop` 以外，還有 `_heapify_max`, `_heappop_max`, `_heapreplace_max`, `_siftdown`, `_siftdown_max`, `_siftup`, `_siftup_max` 這些有趣的東西，不只有各種操作的 max-heap 版本，還有用於維護 `heap` 關鍵的 `_siftdown(heap, startpos, pos)` 和 `_siftup(heap, pos)`，了解這些函式的使用方法就可以做出一些更自由的 `heap` 操作。
話雖這麼說，但我目前也只寫過 [一題](https://colab.research.google.com/drive/1oXmT17Q90hgXNsgoFSGUpwU4nMThOemW?hl=en#scrollTo=nOrrzvdLJ4XU) 有用到這些操作的，主要是為了在不改變值的情況下由 max-heap 切換到 min-heap。

如何找到 `heapq` 純 Python 程式碼？以 Python IDLE 為例，找到 `File -> Open Module`，然後輸入套件名稱就好了！

![image](https://hackmd.io/_uploads/SkVfF0kOJx.png)

注意到 [`heapq.heapify`](https://docs.python.org/zh-tw/3.13/library/heapq.html#heapq.heapify) 的複雜度是 $O(n)$ 且 in-place ，而不是 $O(n \log_2 n)$，因此單純輸入大量數據時可以先全部加入再 `heapify`。

$Time: O(n \log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from heapq import heapify, heappop, heappush
    e = stdin.readline

    n = int(e())
    q = list(map(int, e().split()))
    heapify(q)  # O(n)

    ans = 0
    for _ in range(n - 1):  # 總共合併 n - 1 次
        x = heappop(q) + heappop(q)  # 貪心地取最小兩個合併
        heappush(q, x)  # 合併完放回去
        ans += x  # 增加成本
    print(q[0], ans, sep="\n")
main()
```

### [P-4-9. 基地台](https://judge.tcirc.tw/problem/d049)

常見二分搜考法：對答案二分搜。

[`range(start, stop, step)`](https://docs.python.org/zh-tw/3.13/library/stdtypes.html#ranges) 是一個很有意思的 object，他除了最一般的當作 `iterable` 餵給 `for` 以外，還支援隨機存取，就像一個 `list` 或 `tuple` 一樣，應該說，他的本質就是一個 `sequence`，只是其中所有項都可以從給定的三個 arguments 用數學計算出來，因此記憶體效率十分高。

因為他是一個 `sequence`，所以理所當然地支援 `__iter__`, `__getitem__`, `__len__`, `__reversed__`（當然不能 `__setitem__`），甚至可以用 `slice` 取值、用 `index` 求某個數字在數列裡的位置，超級好用！既然能夠隨機存取，那就當然能夠用 `bisect` 下去二分搜，然而 [`bisect`](https://docs.python.org/zh-tw/3/library/bisect.html#bisect.bisect_left) 直到 Python 3.10 才加入 `key` 引數，因此「對答案二分搜」這個技巧在 APCS 裡還是只能手刻。

反正也不用怕忘記怎麼寫，可以直接把模組原始碼打開，`bisect` 跟 `heapq` 一樣也有寫純 Python 版本。

假設要搜 `[le, ri)` 這個區間，建議用 `bisect(range(ri), val, lo=le, key=func)` 這種寫法，雖然比較不直覺，但這樣可以保證 `range(ri)[x] = x`，不然就得寫 `le + bisect(range(le, ri), val, key=func)`，前面那個 `le +` 豈不是更不直覺？

$Time: O(\text{sort} + n \log_2 R), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left
    e = stdin.readline

    def cover(r: int) -> bool:
        cnt, cov = 0, -1
        for i in p:
            if i > cov:
                cnt += 1
                # 基地台用完 不合
                if cnt > k: return False
                cov = i + r
        return True  # 完整覆蓋

    n, k = map(int, e().split())
    p = sorted(map(int, e().split()))  # 排序各點 才好用掃描線

    # >= Python 3.10 bisect(key)
    # r = 區間長度 // k + 1 必定可完整覆蓋
    print(bisect_left(range((p[-1] - p[0]) // k), True, lo=1, key=cover))
    return  # 下面是舊版本的實作

    # < Python 3.10
    # 維護 [le, ri) 區間
    le, ri = 1, (p[-1] - p[0]) // k
    while le < ri:
        mid = (le + ri) >> 1
        if cover(mid) is True:
            ri = mid
        else:
            le = mid + 1
    print(le)
main()
```

### [P-4-11. 線段聯集](https://judge.tcirc.tw/problem/d050)

基本掃描線。
別忘了結算最後一個線段。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    # 將 (s, t) 線段聯集排列
    l = sorted(tuple(map(int, e().split())) for i in range(n))

    ans = 0
    s = t = -1  # 最後一個線段的起終點
    for i, j in l:
        if i < t:
            # 重疊 更新終點
            if j > t:
                t = j
        else:
            # 未重疊 結算距離 更新新線段
            ans += t - s
            s, t = i, j
    # 結算最後一個線段
    ans += t - s
    print(ans)
main()
```

### [P-4-12. 一次買賣](https://judge.tcirc.tw/problem/d051)

就是當前值減去歷史最小值取大。

$Time: O(n), Space: O(1)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    e()  # n 用不到
    l = map(int, e().split())

    ans = 0
    mn = next(l)  # 最小值 初始化取第一項
    for v in l:
        # 更新最小值
        if v < mn: mn = v
        # 更新所求 (最大盈餘)
        v -= mn  # 盈餘
        if v > ans: ans = v
    print(ans)
main()
```

也可以寫成這樣：

```python=
def main():
    from sys import stdin
    from itertools import accumulate, tee
    e = stdin.readline
    e()  # n 用不到
    l, p = tee(map(int, e().split()))  # 複製兩份 比較好寫
    print(max(map(int.__sub__, l, accumulate(p, min))))
main()
```

### [P-4-13. 最大連續子陣列](https://judge.tcirc.tw/problem/d052)

經典卡丹算法。

以下這種寫法可以用到「更新答案」和「負數不轉移」兩個 case 互斥的特性，但得要題目有說空陣列視為 $0$ 才能這樣寫。不敢說快了多少，心情總歸是比較舒暢。

$Time: O(n), Space: O(1)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    e()  # n 用不到
    dp = ans = 0
    for i in map(int, e().split()):
        dp += i
        if dp > ans:  # 更新答案
            ans = dp
        elif dp < 0:  # 負數不轉移
            dp = 0
    print(ans)
main()
```

<span id="053"></span>

### [Q-4-8. 先到先服務](https://judge.tcirc.tw/problem/d053)

[`heapq.heapreplace`](https://docs.python.org/zh-tw/3.13/library/heapq.html#heapq.heapreplace) 等於先 `heappop` 再 `heappush`，需要和 [`heapq.heappushpop`](https://docs.python.org/zh-tw/3.13/library/heapq.html#heapq.heappushpop) 做出分別，`heappushpop` 就像字面上的一樣是先 `heappush` 再 `heappop`。

$Time: O(n \log_2 m), Space: O(m)$

```python=
def main():
    from sys import stdin
    from heapq import heapreplace
    e = stdin.readline

    n, m = map(int, e().split())
    l = map(int, e().split())

    q = [0] * m
    for i in l:
        # 將新的客人交給最早結束的櫃台處理
        heapreplace(q, i + q[0])
    # 最晚結束的即為所求
    print(max(q))
main()
```

### [Q-4-10. 恢復能量的白雲熊膽丸](https://judge.tcirc.tw/problem/d054)

確認答案的部分有兩種寫法，一種是線性搜，一種是二分搜，就像是 [P-2-15. 圓環出口](#024) 的概念。兩者的複雜度不一樣，前者是 $O(n)$，worst case 就是闖關成功；後者是 $O(k \log_2 n)$，worst case 是 $k = n$ 且一次只過一關，這樣二分搜的範圍縮減很慢，而且搜滿 $k$ 次。

線性搜：
$Time: O(n \times \log_2 \sum l), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left
    e = stdin.readline

    def check(x) -> bool:  # O(n)
        r = cur = 0
        for v in l:
            cur += v
            if cur > x:
                r += 1
                # 藥沒了 到不了
                if r == k: return False
                cur = v
        # 到終點了
        return True

    n, k = map(int, e().split())
    l = map(int, e().split())
    if k == 0:  # 特判: 不能吃藥只能一次幹到底
        print(sum(l))
    elif k == n - 1:  # 特判: 每一回合都吃藥滿能量
        print(max(l))
    else:
        k += 1  # 算上一開始也是滿能量
        l = tuple(l)
        # 對答案二分搜
        # >= Python 3.10 bisect(key)
        print(bisect_left(range(sum(l)), True, lo=max(l), key=check))
        return  # 下面是舊版本的實作

        # < Python 3.10
        # 維護 [le, ri) 區間
        while le < ri:
            mid = (le + ri) >> 1
            if check(mid) is True:
                ri = mid
            else:
                le = mid + 1
        print(le)
main()
```

二分搜：
$Time: O(n + k \log_2 n \times \log_2 \sum l), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_right
    from itertools import accumulate
    e = stdin.readline

    def check(x) -> bool:  # O(klogn)
        idx = 0
        for _ in range(k):
            # 搜下一個能量消耗 > x 的點
            idx = bisect_right(l, l[idx] + x, lo=idx) - 1
            # 成功到底
            if idx >= n:
                return True
        # 在k+1次以內到不了
        return False

    n, k = map(int, e().split())
    l = map(int, e().split())
    if k == 0:  # 特判: 不能吃藥只能一次幹到底
        print(sum(l))
    elif k == n - 1:  # 特判: 每一回合都吃藥滿能量
        print(max(l))
    else:
        k += 1  # 算上一開始也是滿能量
        l = tuple(l)
        le = max(l)
        # 做前綴和 方便二分搜
        # >= Python 3.8 accumulate(initial)
        l = tuple(accumulate(l, initial=0))
        # < Python 3.8
        # l = (0, *accumulate(l))
        ri = l[-1]  # sum(l)

        # 對答案二分搜
        # >= Python 3.10 bisect(key)
        print(bisect_right(range(ri), False, lo=le, key=check))
        return  # 下面是舊版本的實作

        # < Python 3.10
        # 維護 [le, ri) 區間
        while le < ri:
            mid = (le + ri) >> 1
            if check(mid) is True:
                ri = mid
            else:
                le = mid + 1
        print(le)
main()
```

### [P-4-14. 控制點](https://judge.tcirc.tw/problem/d055)

這一題來比較一下我和吳邦一教授寫法上的小差異。

兩段程式的邏輯完全相同，但有一些小小的差異：
首先輸入的部分，「以空白分隔並轉成數字」這個操作在 Python 內有兩種主流寫法，一種是 `[int(x) for x in input().split()]`，一種是 `map(int, input().split())`，這兩者其實不等價，前者是一個 `list`，後者是一個 `iterator`，前者是等價於 `list(map(int, input().split()))`，又後者等價於 `(int(x) for x in input().split())`。以這題來講，傳入 `zip` 中的只需要是 `iterable` 就好了，而 `zip` 回傳的也是 `iterable`，可以直接傳入接收 `iterable` 的 `sorted`，當然轉成 `list` 再 `list.sort()` 也完全沒問題。
但在 `for` 迴圈寫了 `point[::-1]`，這是許多人會忽視的一點：`list[slice]` 必定會複製並建立一個新的 list object，並造成可觀的效能損耗，如果是單純要 iterate 過去的話，可以使用 `reversed(list)`，`reversed` 回傳的是一個 `iterator`，支援 `list`, `tuple`, `str`, `range` 等常見的物件。

在 [AP325 Python 版](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2FmEi9wqzjRCuj2aixy3Ea2Q#P-4-14-%E6%8E%A7%E5%88%B6%E9%BB%9E2D-max) 中，這題的範例解法：

```python=
# P-4-14 2d max subarray, backward, O(nlogn)
n = int(input())
px = [int(x) for x in input().split()]
py = [int(x) for x in input().split()]
point = list(zip(px,py))
point.sort() # smaller x, if x1=x2 then smaller y
max_y = -1 # currently max y
total = 0 # number of maximal points
for x,y in point[::-1]: # backward
    if y > max_y:
        total += 1 # a new maximal point
        max_y = y # update
#
print(total) 
```

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    e()  # n 用不到
    # x降冪 再y降冪
    p = sorted(zip(map(int, e().split()), map(int, e().split())), reverse=True)

    ans = 0
    my = -1  # 目前最大 y 初始化為 -1 確保無法控制任何點
    for y in map(itemgetter(1), p):
        # 因為此點 x <= 右邊所有掃過的
        # 所以只有 y >  右邊最大y(前一個控制點之y)時
        # 這個點才不會被控制 而必須加進來
        # 至於x相同時 y在降冪 所以不會重複取到
        if y > my:
            ans += 1
            my = y
    print(ans)
main()
```

### [P-4-15. 最靠近的一對](https://judge.tcirc.tw/problem/d056)

掃描線的寫法怎麼優化呢？既然 `sortedcontainers.SortedList` 沒有內建，就自己手刻吧！
比較麻煩的是，這題不只要實作 `add`，還有 `remove`、`irange` 要實作。`expand` 函數在很多地方都有用到，就把他獨立出來了；`remove` 的邏輯則由 `_delete` 實際執行，刪除後要確保塊夠長，否則要跟其他塊合併；`irange` 則二分搜後手動於塊與塊之間遍歷即可。

`SortedList` 原始碼：

```python=
def _delete(self, pos, idx):
    _lists = self._lists
    _maxes = self._maxes
    _index = self._index

    _lists_pos = _lists[pos]  # 快取目標塊

    del _lists_pos[idx]  # 直接硬刪
    self._len -= 1  # 更新總長度

    len_lists_pos = len(_lists_pos)  # 目標塊新長度

    if len_lists_pos > (self._load >> 1):  # 夠長
        _maxes[pos] = _lists_pos[-1]  # 更新最大值即可
        # !seg.update(pos,-1)
        if _index:  # 維護用於 index 取值的線段樹
            child = self._offset + pos
            while child > 0:
                _index[child] -= 1
                child = (child - 1) >> 1
            _index[0] -= 1
    elif len(_lists) > 1:  # 不夠長 有其他塊可以合併
        if not pos:  # 如果左邊沒塊就將索引往右一格
            pos += 1

        prev = pos - 1  # 向左合併
        _lists[prev].extend(_lists[pos])
        _maxes[prev] = _lists[prev][-1]

        # 刪除右塊
        del _lists[pos]
        del _maxes[pos]
        # 需要重種 index 線段樹
        del _index[:]

        self._expand(prev)  # 維護合併後新塊的長度
    elif len_lists_pos:  # 不夠長 但只有自己這塊 代表總長度尚短
        _maxes[pos] = _lists_pos[-1]  # 更新最大值即可
    else:  # SortedList 全空
        del _lists[pos]
        del _maxes[pos]
        del _index[:]
```

以下的程式碼中比較難以理解的可能是 `expand_i` 這個變數以及其相關邏輯，他的功能是「處理上一輪 iterate 的 `expand(i)` 操作」，並負責把 `i` 暫存起來。為何要讓 `expand` 操作隔一輪延後執行？在 `remove` 後，如果當前塊太短，就會跟左邊的塊合併，合併後需要呼叫一次 `expand` 維護新塊長，但因為左邊的塊較右塊長，下一輪要刪除的值可能在左塊尾端，`expand` 後會跑去右塊，這樣索引就爛掉了。因此為了避免這種情況發生，間隔一個 iterate，也就是保證間隔一塊以上即可。

$Time: O(n \sqrt n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_right, insort_right
    e = stdin.readline
    inf = float("INF")

    def expand(i):  # SortedList._expand
        chunk = sl[i]  # 取要 expand 的塊
        if len(chunk) > (LOAD << 1):  # 如果塊過長
            # 切半
            half = chunk[LOAD:]
            del chunk[LOAD:]
            mx[i] = chunk[-1]  # 更新左半最大值
            # 插入右半塊
            sl.insert(i + 1, half)
            mx.insert(i + 1, half[-1])

    n = int(e())
    LOAD = int((n >> 1) ** 0.5)  # SortedList 理想塊長
    # x升冪 再y升冪
    l = sorted(tuple(map(int, e().split())) for i in range(n))

    ans = inf
    # 先前的 (y, x) 照 y 升冪排序
    sl = []  # 模擬 SortedList
    mx = []  # SortedList 每一區塊的最後一項 方便二分搜
    rmv = []  # 要刪除的點 按照塊index分類
    expand_i = None  # 延後一個 iterate 再做 expand chunk
    for x, y in l:
        if not mx:  # 如果 SortedList 為空
            # 直接插入
            val = (y, x)
            sl.append([val])
            mx.append(val)
            continue

        # 二分搜y值下界
        val = (y - ans, inf)
        if val < mx[-1]:  # 如果下界不存在就跳過
            i = bisect_right(mx, val)
            chunk = sl[i]
            nc = len(chunk)
            j = bisect_right(chunk, val)
            py, px = chunk[j]

            rmv.clear()
            ci = js = None
            while py < y + ans:
                if px <= x - ans:  # 出界 要刪除
                    if i != ci:  # 要刪除的點在新的塊內
                        ci, js = i, []
                        rmv.append((ci, js))
                    js.append(j)
                else:
                    # 更新最短距離
                    ans = min(ans, abs(x - px) + abs(y - py))
                # 遍歷下一個點
                j += 1
                if j == nc:  # 此塊結束
                    j = 0
                    i += 1  # 找下一塊
                    if i == len(sl): break  # 到底
                    chunk = sl[i]
                    nc = len(chunk)
                py, px = chunk[j]  # 取點

            # 由右側往左側刪除 index 才不會改變
            for i, js in reversed(rmv):
                # 單塊內刪除
                chunk = sl[i]
                for j in reversed(js):
                    del chunk[j]
                # expand 上一個該 expand 的塊
                if expand_i is not None:
                    expand(expand_i)
                    expand_i = None
                # 維護塊長
                nc = len(chunk)
                if nc > (LOAD << 1):  # 長度夠
                    mx[-1] = chunk[-1]  # 維護最大值即可
                elif len(mx) > 1:  # 長度不夠 可以合併
                    if i: i -= 1  # 預設向左合併
                    sl[i].extend(sl[i + 1])
                    mx[i] = sl[i][-1]
                    del sl[i + 1]
                    del mx[i + 1]
                    expand_i = i  # 合併後須要維護塊長
                elif nc:  # 長度不夠 但只有此塊 即SortedList本身很短
                    mx[-1] = chunk[-1]  # 維護最大值即可
                else:  # 清空 SortedList
                    del sl[i]
                    del mx[i]
            # expand 最後一組
            if expand_i is not None:
                expand(expand_i)
                expand_i = None

        # 插入新點
        val = (y, x)
        if not mx:  # 如果 SortedList 為空
            # 直接插入
            val = (y, x)
            sl.append([val])
            mx.append(val)
        elif val >= mx[-1]:  # 特判插入尾端
            sl[-1].append(val)
            mx[-1] = val
            expand(len(mx) - 1)  # 維護塊長
        else:  # 插入中間
            i = bisect_right(mx, val)
            insort_right(sl[i], val)
            expand(i)  # 維護塊長
    print(ans)
main()
```

還有 $O(n \log_2 n)$ 的分治解、$O(n)$ 的神奇隨機解、一次 `sort` 後線性解的「人類智慧」之極致展現，就賣個關子留到 [第五章節](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part2#P-5-5-%E6%9C%80%E9%9D%A0%E8%BF%91%E7%9A%84%E4%B8%80%E5%B0%8D) 吧，不然那章好空虛 qwq。

### [Q-4-16. 賺錢與罰款](https://judge.tcirc.tw/problem/d057)

經典貪心。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    # 貪心策略: 製作時間短的先
    l = sorted(zip(map(int, e().split()), map(int, e().split())))

    now = ans = 0
    for t, d in l:
        now += t  # 累加時間
        ans += d - now  # 賺賠錢
    print(ans)
main()
```

稍微觀察一下可以發現 `d` 直接求和就好了，跟 `t` 根本沒有關係。

```python=
def main():
    from sys import stdin
    from itertools import accumulate
    e = stdin.readline

    e()  # n 用不到
    # 時間升冪排序 對前綴和累加 是扣款
    # 工資直接加總就好了
    print(-sum(accumulate(sorted(map(int, e().split()))))
          + sum(map(int, e().split())))
main()
```

### [Q-4-17. 死線高手](https://judge.tcirc.tw/problem/d058)

中一中的裁判機不快，新的 Judge 又沒有對 Python 開比較大的時限，這題就算用上了 PyPy 再加上輸出優化還是過不了。

可以到 [惠文高中的 Judge](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a205) 測試。

$Time: O(t \times (\text{sort} + n)), Space: O(n)$

```python=
def main():
    from sys import stdin
    e = stdin.readline

    e()  # 測資數量 用不到
    for _ in stdin:  # 每筆測資輸入的第一行是n 用不到
        t = map(int, e().split())  # 時間
        d = map(int, e().split())  # 死線
        now = 0
        # 死線早的先處理
        for d, t in sorted(zip(d, t)):
            now += t  # 累加時間
            if now > d:  # 超過死線
                print("no")
                break
        else:  # 全部完成
            print("yes")
main()
```

### [Q-4-18. 少林寺的櫃姐](https://judge.tcirc.tw/problem/d059)

就是 [Q-4-8. 先到先服務](#053) 再加上「對答案二分搜」。

看到這題的時間複雜度，我實在得澄清一點：$\log_2^2n = \log_2 (\log_2 n) \ne (\log_2 n)^2$。這兩者不知道甚麼時候開始就在競程領域被瘋狂地誤用，但 $\log$ 可不是三角函數啊！
（雖然但是 $\sin^2 x = (\sin x)^2 \ne \sin (\sin x)$ 這種不一致的規定也很解就是了）

$Time: O(n \times (\log_2 n)^2), Space: O(n)$

```python=
def main():
    from sys import stdin
    from bisect import bisect_left
    from heapq import heapreplace
    e = stdin.readline

    def check(x) -> bool:  # O(nlogx)
        q = [0] * x
        for i in l:
            # 將新的客人交給最早結束的櫃台處理
            heapreplace(q, i + q[0])
        # 最晚結束的即為所求
        return max(q) <= k

    n, k = map(int, e().split())
    l = tuple(map(int, e().split()))

    # >= Python 3.10 bisect(key)
    # 下界要設定成 1 不然 check(0) 會讓 q[0] IndexError
    print(bisect_left(range(n), True, lo=1, key=check))
    return  # 下面是舊版本的實作

    # < Python 3.10
    le, ri = 1, n
    while le < ri:
        mid = (le + ri) >> 1
        if check(mid) is True:
            ri = mid
        else:
            le = mid + 1
    print(le)
main()
```

### [Q-4-19. 五嶽盟主的會議場所](https://judge.tcirc.tw/problem/d060)

「按照開始時間排序」可以確保更早到場的人一定已經掃過了，並保證已經下山的人之後不會再用到，使用 heap 可以讓他們依序下山。

$Time: O(n \log_2 n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from heapq import heappush, heappop
    from operator import itemgetter
    e = stdin.readline

    e()  # n 用不到

    ans = cur = 0
    q = [(float("INF"), 0)]  # 結束時間 sentinel 為無限
    # 按照開始時間排序
    for m, s, t in sorted((tuple(map(int, e().split()))
                           for i in range(n)), key=itemgetter(1)):
        while q[0][0] < s:  # 讓結束的門派下山
            _, v = heappop(q)
            cur -= v  # 減去下山人數
        cur += m  # 加上上山人數
        if cur > ans: ans = cur  # 更新最多人數
        heappush(q, (t, m))  # 紀錄下山時間
    print(ans)
main()
```

### [Q-4-20. 監看華山練功場](https://judge.tcirc.tw/problem/d061)

根據題意應該可以猜出要貪心，先想想看甚麼狀況下可以貪：

- case 1:
```c++=
#####
   ######
       ######  <- new
```
這個貪不了，區間 1, 2 都要留著，還得加入 3。

- case 2:
```c++=
#######
   #########
     #####  <- new
```
可以看出區間 3 沒有存在的必要，不用加入。

- case 3:
```c++=
#######
   ######
     ########  <- new
```
這次變成區間 2 沒有存在的必要，可以刪掉 2 並加入 3。

因此，我們可以先將各區間按照起始點排列，再依據上面的三個 case 判斷就好了。

需要注意的是 case 3 判斷的部分，可能需要考慮要不要加上 `while`，當然如果不確定的話加上絕對不會錯，仔細思考一下：三個區間都留下的情況只有 case 1，條件是區間 1, 3 沒有重疊，假設再加上一個區間 4 和區間 2 有重疊，這樣 2, 3, 4 會形成 case 3，刪除 3 並加入 4，接下來如果再檢查一次 case 3 會發現 4, 1 沒有重疊，因為區間 4 的起點必定比 3 還要後面，不可能與 1 重疊。因此 case 3 最多觸發一次，用 `if` 就好了。
```c++=
#####
   #######
       ######  <- case 1
        ######  <- new - case 3 - delete 3
```

題目要求覆蓋 $[x, y]$，我們可以假裝已經加入了一個 $[-1, x]$ 區間，左端點 $-1$ 確保他，$y$ 就只要看右端點覆蓋到的時候就結束就好了。

因為一次需要判斷三個區間之間的關係，因此快取 Stack 的最後兩項。

$Time: O(\text{sort} + n), Space: O(n)$

```python=
def main():
    from sys import stdin
    from heapq import heappush, heappop
    e = stdin.readline

    n = int(e())
    x, y = map(int, e().split())
    l = sorted((tuple(map(int, e().split())) for i in range(n)))

    # 儲存結束點的stack 單調遞增
    stk = []
    pop, append = stk.pop, stk.append  # 快取函數
    # stack的最後兩項 初始化為 sentinel, 第一區間
    pp, p = -1, x
    for s, t in l:
        if s > p:  # 區間不連續
            print(-1)
            return
        if t <= p:  # 此區間沒有存在必要 - case 2
            continue
        if s <= pp:  # 如果前一個區間不必要就pop掉 - case 3
            p, pp = pp, pop()
        append(pp)  # 加入此區間
        pp, p = p, t
        if t >= y:  # 達成條件 輸出所求
            break
    else:
        # 沒有break出來 代表區間右端沒有到y
        print(-1)
        return
    # 即為所求 (最後兩項在p,pp中 但扣掉初始化時預填的兩項剛好消掉)
    print(len(stk))
main()
```

## 附件

- [AP325 初見](https://colab.research.google.com/drive/1LyBHbqB0n2lFb1Lt_7EM0gbBOfDTC2H1?hl=en) - 這篇是第一次刷 AP325 時寫的，時間跨距稍微有點大，可以看到很噁心的寫法和最佳解交雜，比較亂，屬於單純的歷程記錄。
- [AP325 二見](https://colab.research.google.com/drive/1lcYD5MQF2cVF3rQ725gSnsKtFc-NcRS-?hl=en) - 這篇即是本文所有程式碼的來源。
- [AP325 精熟到登峰 上篇](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1) - 本文連結
- [AP325 精熟到登峰 下篇](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part2) - 下篇連結

## 參考資料

- [AP325](https://drive.google.com/drive/u/0/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) by 吳邦一教授
- [AP325-Python](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2Fg2kqHh5_Q4eQnz-mfNu3Kw) by 吳邦一教授
