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

🔗 ABC435F Cat exercise

rating: 1368

Problem Statement

題目簡述

有 $N$ 個貓塔排成一列，高度 $P_1, \dots, P_N$ 是 $1 \dots N$ 的排列。貓一開始在高度為 $N$ 的塔上（全域最高點）。
高橋可以反覆選擇並移除塔。當貓所在的塔被移除時，貓會移動到「從當前位置出發，只經過相鄰且未被移除的塔所能到達的」所有塔中高度最高的一個。
移動距離為塔的索引差絕對值。若無處可去，遊戲結束。
求貓在遊戲結束前能移動的最大總距離。注意：移除塔後空位不會填補，相鄰關係即斷開。

Constraints

約束條件

$1 \le N \le 2 \times 10^5$
$(P_1, \dots, P_N)$ 是 $(1, \dots, N)$ 的一個排列。
所有輸入為整數。

思路：分治 (Divide and Conquer) + 貪心 (Greedy)

這道題目可以使用 分治 (Divide and Conquer) 的思想來解決。

1. 問題拆解

假設貓目前可以到達的位置為 $[l, r]$ 區間，且目前位於區間內的最高點 $pos$ 。
當移除這個最高點 $pos$ 時，原本的相鄰關係被打斷，整個區間被分割成兩個獨立的子區間：

左區間： $[l, pos-1]$
右區間： $[pos+1, r]$

根據移動規則，貓原本會移動到這兩個區間中「高度最高」的那個塔（即兩個子區間最大值中的較大者）。
然而，題目允許我們在移除 $pos$ 之前先移除其他的塔。利用這一點，我們可以預先移除某一側的所有塔，迫使貓只能跳往另一側。
這讓我們在每一步都擁有 「向左走」或「向右走」的選擇權，從而將問題轉化為一個可以取最大值的遞迴決策問題。

定義子問題

定義 $dfs(l, r, pos)$ 代表貓目前位於 $pos$ 位置，目前可移動的範圍為 $[l, r]$ ，所能獲得的最大總移動距離。
其中 $pos$ 必為 $[l, r]$ 區間內的最大值索引

2. 貪心決策 (Greedy)

基於上述討論，對於當前區間 $[l, r]$ 及其最大值位置 pos，我們有兩個選擇：

選擇往左側 ( $l \dots pos-1$ )
選擇往右側 ( $pos+1 \dots r$ )

我們應該選擇這兩條路徑中，總收益（當前移動距離 + 後續遞迴收益）最大 的那一條。

在選定方向（例如向左）後，理論上我們可以通過預先移除某些比目標點更高的塔，讓貓跳到該側任意一個位置。
但最佳策略是直接前往該側最高的塔 $pos_L$ 。

證明：為何應直接選擇局部最大值？

設 $u$ 、 $v$ 、 $w$ 分別為當前點、區間最大值點、任意其他目標點的位置。
假設我們想跳過 $v$ 直接從 $u \to w$ 。由於 $v$ 的高度大於 $w$ ，貓會優先去 $v$ 。
因此，為了去 $w$ ，我們必須先移除 $v$ （或使其不可達）。

此時有兩種可能：

移除 $v$ 後導致路徑中斷（即 $v$ $v$ 位於 $u, w$ $u, w$ 之間）：
- 此時 $u$ 無法到達 $w$ ，策略失敗。
移除 $v$ 不影響到達 $w$ （路徑未斷）：
- 根據 三角不等式： $|u - v| + |v - w| \ge |u - w|$ 。
- 等號成立當且僅當 $v$ 位於 $u, w$ 之間，但這屬於情況 1（會破壞可達性）。
- 因此在情況 2 下，嚴格不等式成立，先去 $v$ 的距離收益更高。

結論：跳過 $v$ 要麼導致不可達，要麼收益更低，因此不跳過 $v$ 一定更優。

3. 預處理 Range Maximum Query (RMQ)

為了快速找到任意區間的最大值位置，我們可以使用 稀疏表(Sparse Table) 進行預處理。這樣查詢區間最大值的時間複雜度為 $O(1)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ 。
- Sparse Table 建構： $\mathcal{O}(n \log n)$ ，用於 $\mathcal{O}(1)$ 查詢區間最大值索引。
- 分治求解： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n \log n)$ 。主要用於存儲 Sparse Table 結構。

為什麼分治是

\mathcal{O}(n)

？—— 與笛卡爾樹的關聯

整個分治遞迴過程本質上是在遍歷數列對應的 笛卡爾樹 (Cartesian Tree)。

結構對應：笛卡爾樹滿足 堆積性質（父節點 > 子節點）與 中序遍歷有序性。題目中尋找區間最大值並劃分左右子區間的過程，等價於從樹根向下訪問左右子節點。
線性複雜度：由於序列中每個元素恰好對應笛卡爾樹上的一個節點，且遞迴過程中每個節點僅被訪問一次，故總時間複雜度為線性。

Code

import sys
sys.setrecursionlimit(int(2e5 + 5))

class SparseTable:
    def __init__(self, data, merge_func):
        n = len(data)
        self.data = data
        self.merge = merge_func
        k = n.bit_length() - 1
        self.st = [[None] * (k + 1) for _ in range(n)]
        for i in range(n):
            self.st[i][0] = data[i]
        
        for j in range(1, k + 1):
            for i in range(n):
                self.st[i][j] = self.merge(self.st[i][j - 1], self.st[min(n - 1, i + (1 << (j - 1)))][j - 1])
    
    def query(self, L, R):  # 0-indexed
        k = (R - L + 1).bit_length() - 1
        return self.merge(self.st[L][k], self.st[R - (1 << k) + 1][k])

fmax = lambda a, b: a if a > b else b

def solve():
    n = int(input())
    A = list(map(int, input().split()))

    mp = {x : i for i, x in enumerate(A)}
    st = SparseTable(A, fmax)

    def dfs(l: int, r: int, pos: int) -> int:
        if l >= r:
            return 0
        res = float('-inf')
        if l <= pos - 1:
            x = st.query(l, pos - 1)
            res = fmax(res, abs(pos - mp[x]) + dfs(l, pos - 1, mp[x]))
        if pos + 1 <= r:
            x = st.query(pos + 1, r)
            res = fmax(res, abs(pos - mp[x]) + dfs(pos + 1, r, mp[x]))
        return res

    print(dfs(0, n - 1, mp[n]))

if __name__ == "__main__":
    solve()