Codeforces 🟢 CF2128D. Sum of LDS

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

🔗 🟢 CF2128D. Sum of LDS

Problem Statement

題目簡述

給定一個長度為 $n$ 的排列 $p$，且對所有 $1 \le i \le n-2$ 皆滿足 $\max(p_i, p_{i+1}) > p_{i+2}$。
定義 $\mathrm{LDS}(A)$ 為陣列 $A$ 的最長遞減子序列長度。請計算所有子陣列 $[p_l,\ldots,p_r]$ 的 $\mathrm{LDS}$ 之總和。

Constraints

---

思路：動態規劃

1. 關鍵性質：每個後綴的最大值只可能在前兩個位置

題目保證對所有 $i$ 都有：

$$\max(p_i,p_{i+1})>p_{i+2}$$

這個條件等價於：在任意連續三個位置中，第三個元素不可能同時比前兩個都大。

因此對任何固定起點 $i$，考慮後綴 $[p_i,p_{i+1},\ldots,p_n]$ 的最大值在哪裡。

• 假設最大值出現在某個位置 $k\ge i+2$，那麼它會滿足 $p_k>p_{k-1}$ 且 $p_k>p_{k-2}$。
• 但套用題目條件在 $k-2$ 上：$\max(p_{k-2},p_{k-1})>p_k$，矛盾。

所以後綴最大值不可能在 $i+2$ 之後出現，只能在 $i$ 或 $i+1$：

核心觀察

後綴 $[i..n]$ 的最大元素一定是 $p_i$ 或 $p_{i+1}$。

這個性質就是整題能 $\mathcal{O}(n)$ 解的核心。

2. 定義狀態：固定左端點的所有子陣列 LDS 總和

令陣列為 $p[0..n-1]$，根據題意，我們需要計算所有子陣列的 LDS 總和，寫成數學式即為：

$$\text{ans} = \sum_{0 \le l \le r < n} \text{LDS}(p[l..r])$$

固定左端點 $i$，定義 $f[i]$ 為所有左端點固定在 $i$ 的子陣列，它們的 LDS 長度總和：

$$f[i] = \sum_{r=i}^{n-1} \text{LDS}(p[i..r])$$

那答案就是把所有左端點加總：

$$\text{ans}=\sum_{i=0}^{n-1} f[i]$$

接下來只要找到 $f[i]$ 的遞迴式即可。

3. 狀態轉移：根據後綴最大值位置分兩種情況

情況 A：$p_i > p_{i+1}$

由「後綴最大值只可能在 $i$ 或 $i+1$」可知，此時後綴最大值就是 $p_i$。

因此對任何 $r\ge i$，在子陣列 $[i..r]$ 裡，$p_i$ 是最大元素。

為什麼 LDS 一定可以選 $p_i$ 當開頭？

因為 decreasing subsequence 開頭需要「夠大」，而 $p_i$ 比子陣列裡所有其他元素都大，所以：

• 任意在 $[i+1..r]$ 裡的遞減子序列，前面都可以安全加上 $p_i$，長度 +1
• 也不會比不選 $p_i$ 更差（一定更好或至少同樣好）

所以有：

$$\text{LDS}(p[i..r]) = 1 + \text{LDS}(p[i+1..r])$$

把 $r$ 從 $i + 1$ 加到 $n - 1$，再加上新增的 $[i..i]$ ：

$$f[i]=1 + \sum_{r=i + 1}^{n-1} \bigl(1+\text{LDS}(p[i+1..r])\bigr) = (n-i) + f[i+1]$$

情況 B：$p_i < p_{i+1}$

同理可知後綴最大值變成 $p_{i+1}$。

對於任何 $r\ge i+1$ 的子陣列 $[i..r]$：

• 最大元素是 $p_{i+1}$，一個最長遞減子序列一定可以以它開頭
• 但 $p_i$ 在 $p_{i+1}$ 之前，且 $p_i<p_{i+1}$，所以 不可能 出現在同一條遞減序列的開頭位置（因為要遞減，前面要更大）

因此對 $r\ge i+1$：

$$\text{LDS}(p[i..r]) = \text{LDS}(p[i+1..r])$$

唯一特例是 $r=i$（子陣列只有 $[p_i]$）：

$$\text{LDS}(p[i..i])=1$$

所以：

$$f[i] = 1 + \sum_{r=i+1}^{n-1}\text{LDS}(p[i+1..r]) = 1 + f[i+1]$$

結合兩種情況的遞迴式

$$f[i] = \begin{cases} f[i+1] + (n-i) & \text{if } p_i > p_{i+1} \\ f[i+1] + 1 & \text{if } p_i < p_{i+1} \end{cases}$$

其中 $f[n]=0$。

最終答案

所求的答案就是 $\displaystyle\sum_{i=0}^{n-1} f[i]$。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$（每個位置做 $\mathcal{O}(1)$ 計算）
• 空間複雜度：$\mathcal{O}(n)$（儲存每個左端點的狀態值）

---

Code

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

    # f[i] 表示以 i 為左端點的所有子陣列的 LDS 總和
    f = [0] * (n + 1)

    # 從右往左計算
    for i in range(n - 1, -1, -1):
        if i + 1 < n and P[i] > P[i + 1]:
            f[i] = f[i + 1] + (n - i)
        else:
            f[i] = f[i + 1] + 1
    print(sum(f))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()