題目要求
序列長度 n ≤ 200,000,支持兩種操作:單點修改值、查詢區間 [L,R] 内最長連續遞增子序列(LCIS)長度。操作數 m ≤ 200,000。
線段樹節點信息設計
每個節點維護區間 [l,r] 的以下信息:
- `lnum`、`rnum`:區間最左/最右端點的值
- `llen`:以左端點開始的最長連續遞增前綴長度
- `rlen`:以右端點結束的最長連續遞增後綴長度
- `mlen`:區間內最長連續遞增子序列長度
合併操作
父節點由左右子節點合併:
- 邊界值直接取自左右子節點
- 若左子節點右端值 < 右子節點左端值,可合併跨越中點的遞增段:
`llen` = 左子節點全段遞增 ? 左長 + 右前綴 : 左前綴
`rlen` = 右子節點全段遞增 ? 右長 + 左後綴 : 右後綴
`mlen` = max(左mlen, 右mlen, 左後綴 + 右前綴)
- 否則無法跨越合併,各值直接取子節點對應值
查詢處理
查詢時同樣需合併左右子樹結果,注意邊界重疊:跨越中點的合併長度受查詢區間左右邊界限制,取 `min(左子樹查詢範圍長度, 左後綴) + min(右子樹查詢範圍長度, 右前綴)`。
複雜度
建樹 O(n),單點修改 O(log n),區間查詢 O(log n)。總複雜度 O((n+m) log n),滿足限制。