HDU 3564 Another LIS：線段樹找第 k 空位 + LIS 經典 DP

題目大意

初始空序列，依次插入數字 1..N。第 k 次插入：數字 k 插入位置 Xₖ（0-based，即當前序列長度為 k-1，Xₖ ∈ [0, k-1]）。每次插入後輸出當前序列的 LIS 長度。
N ≤ 10⁵，T ≤ 10。

關鍵轉化：離線求最終位置，再做 LIS

• 最終序列長度 N，每個數字 k 有一個確定位置 pos[k]。
• 插入操作「在當前序列位置 Xₖ 插入」等價於：在長度 N 的空陣列中，從右向左處理 k = N..1，每次在「剩餘空位」中找第 Xₖ+1 個空位放入 k。
• 此過程可用線段樹維護區間空位數，單次查找/更新 O(log N)。

線段樹找第 k 空位

• 節點存 sum = 該區間空位數。
• 查找第 k 空位：遞迴下降，若左子樹 sum ≥ k 走左，否則 k -= left.sum 走右。
• 初始 build(1, N) 全為空（sum = r-l+1）。

求 LIS：標準 O(N log N) 貪心 + 二分

• 得到位置陣列 pos[1..N] 後，按數字順序 k = 1..N 遍歷 pos[k]。
• 維護 dp[len] = 長度為 len 的上升子序列的最小末尾值（此處為位置）。
• 對每個 pos[k]，二分找最大 len 使 dp[len] < pos[k]，更新 dp[len+1] = pos[k]，答案 = 最大 len。

完整流程

for each test case:
    read N, X[1..N]
    build segtree(1, N)
    for k = N down to 1:
        pos[k] = query_kth_empty(X[k] + 1) // 1-based kth empty
        update(pos[k], occupied)
    // now pos[1..N] is final positions
    len = 0
    for k = 1 to N:
        idx = lower_bound(dp+1, dp+len+1, pos[k]) - dp
        dp[idx] = pos[k]
        len = max(len, idx)
        print len
    print blank line

複雜度

• 構建位置 O(N log N)，LIS O(N log N)，總 O(N log N)。
• 記憶體 O(N)。

總結

本題將「動態插入序列求 LIS」轉化為「離線確定最終位置 + 靜態 LIS」。線段樹「找第 k 個空位」是經典操作（如順序統計樹），配合標準 LIS 貪心二分，構成完整解法。思路清晰，代碼模組化程度高。