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

🔗 🟢 AT_dp_q Flowers

Problem Statement

題目簡述

有 $N$ 朵花排成一列，第 $i$ 朵花高度為 $h_i$ （兩兩互異），美麗值為 $a_i$ 。現需移除若干花，使剩餘花從左到右高度嚴格遞增，求剩餘花美麗值總和的最大值。

Constraints

約束條件

$1 \le N \le 2 \times 10^5$
$1 \le h_i \le N$ ，且 $h_1, h_2, \ldots, h_N$ 兩兩不同
$1 \le a_i \le 10^9$

思路：線段樹優化 DP

本題是 帶權 LIS（Longest Increasing Subsequence） 的變種。我們不再追求子序列長度最長，而是選取一個高度嚴格遞增的子序列，使美麗值總和最大化。

DP 定義

設 $f[h]$ 表示「以高度恰好為 $h$ 的花作為子序列結尾時，所能達成的最大美麗值總和」。

對於按原始順序從左到右掃描到的第 $i$ 朵花（高度 $h_i$ 、美麗值 $a_i$ ），其轉移為：

f[h_i] = \max_{0 \le j < h_i} f[j] + a_i

關鍵觀察

由於花的高度 $h_i$ 兩兩互異且 $1 \le h_i \le N$ ，可直接以高度值作為線段樹的索引，無需離散化。

正確性

從左到右掃描時，線段樹僅含位置 $< i$ 的花。查詢 $\max_{j < h_i} f[j]$ 自動滿足「位置靠左 ∧ 高度較小」的雙重限制。

線段樹優化

樸素 DP 需要 $O(N)$ 時間查詢前綴最大值，總複雜度 $O(N^2)$ 無法接受。
使用 單點修改、區間最大值查詢 的線段樹，可將每次轉移優化至 $O(\log N)$ ：

seg.prod(0, h)：查詢高度 $< h$ 的所有花中，已累積的最大美麗值（前綴 $[0, h)$ 的最大值）
seg.set(h, val)：更新以高度 $h$ 結尾的最佳結果

最終答案為 seg.all_prod()，即所有狀態的最大值。

複雜度分析

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

Code

from atcoder.segtree import SegTree

def solve():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    
    # seg[h] = 以高度 h 結尾的子序列最大美麗值
    seg = SegTree(max, 0, N + 1)
    for h, x in zip(H, A):
        f = seg.prod(0, h) + x  # 查詢高度 < h 的最大值，加上當前美麗值
        seg.set(h, max(seg.get(h), f))  # 更新以高度 h 結尾的最佳結果
    print(seg.all_prod())

if __name__ == "__main__":
    solve()