首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

HDU 3308 LCIS:線段樹維護區間最長連續遞增子序列

     編輯:C++ 入門

題目要求

序列長度 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),滿足限制。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved