題目的難度顏色使用 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]$ ，所能獲得的最大總移動距離。

2. 貪心決策 (Greedy)

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

選擇往左側 ( $l \dots pos-1$ )：
- 操作：保留左側，並移除右子區間的所有塔，迫使貓往左跳。
- 落點：左區間最大值 $pos_L$ （後續證明其最優性）。
- 收益： $|pos - pos_L| + \text{dfs}(l, pos-1, pos_L)$ 。
選擇往右側 ( $pos+1 \dots r$ )：
- 操作：保留右側，並移除左子區間的所有塔，迫使貓往右跳。
- 落點：右區間最大值 $pos_R$ （後續證明其最優性）。
- 收益： $|pos - pos_R| + \text{dfs}(pos+1, r, pos_R)$ 。

我們應該選擇這兩條路徑中，總收益（當前移動距離 + 後續遞迴收益）最大 的那一條。
在選定方向（例如向左）後，理論上我們可以通過預先移除某些比目標點更高的塔，讓貓跳到該側任意一個位置。但最佳策略是直接前往該側最高的塔 $pos_L$ 。

證明：為何應直接選擇局部最大值？ (三角不等式)

假設我們目前位於 $u$ ，並決定往左側移動。
令左側區間的最大值位於 $v$ 。理論上，我們可以透過預先移除左側區間中比目標點更高的塔，讓貓跳過 $v$ ，直接跳到左側區間中更遠的某個點 $w$ 。

比較兩種策略：

跳過 $v$ 直接去 $w$ ：
- 單步收益： $|u - w|$
- 後續狀態：位於 $w$ ，面對 $w$ 的子問題。
- 總收益 $S_1 = |u - w| + \text{Future}(w)$
先去 $v$ ，再從 $v$ 去 $w$ ：
- 第一步收益： $|u - v|$
- 第二步收益： $|v - w|$ (從 $v$ 往 $w$ 方向走)
- 後續狀態：位於 $w$ ，面對 $w$ 的子問題。
- 此路徑總收益 $S_2 = (|u - v| + |v - w|) + \text{Future}(w)$

根據 三角不等式：

|u - w| \le |u - v| + |v - w|

這意味著 $S_1 \le S_2$ 。

結論：直接跳到 $w$ 的收益（ $S_1$ ）永遠不會超過「先停在 $v$ 再去 $w$ 」的收益（ $S_2$ ）。
此外，到達 $v$ 後，我們其實不一定要去 $w$ ，還可以選擇去 $v$ 的另一側，若那樣更優。因此，保留 $v$ 作為中繼點，不僅在距離上穩賺不賠，還保留了更多選擇權。

3. 實作細節

RMQ 問題：為了快速找到任意區間的最大值位置，我們可以使用 稀疏表(Sparse Table) 進行預處理。這樣查詢區間最大值的時間複雜度為 $O(1)$ 。
遞迴函數 dfs(l, r, pos)：
- 終止條件：當 $l \ge r$ 時，區間為空或只剩一個塔（即貓所在的塔），無法再移動，返回 $0$ 。
- 計算左側收益：查詢 $query(l, pos-1)$ 得到 $pos_L$ ，計算 $|pos - pos_L| + dfs(l, pos-1, pos_L)$ 。
- 計算右側收益：查詢 $query(pos+1, r)$ 得到 $pos_R$ ，計算 $|pos - pos_R| + dfs(pos+1, r, pos_R)$ 。
- 返回兩者之大者。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N)$ $O (N lo g N)$ 。
- Sparse Table 建構： $\mathcal{O}(N \log N)$ 。
- 分治： $\mathcal{O}(N)$ 。分治的結構等價於遍歷序列所隱含的笛卡爾樹（Cartesian Tree），每個節點恰好被訪問一次，且每次查詢最大值位置為 $\mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(N \log N)$ 。用於存儲 Sparse Table。

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()