BZOJ 3173 [TJOI2013] 最長上升子序列：動態插入+樹狀數組優化（O(N log N)）

題目：初始空序列，依次將 1..N 插入指定位置 X_k (0 ≤ X_k ≤ k-1)。每次插入後輸出當前序列的 最長上升子序列 (LIS) 長度。N ≤ 100,000。

核心洞察

1. 逆向思維：最終序列確定後，每個數 k 的最終位置 pos[k] 可通過 樹狀數組 (BIT) 反推：從 N 遞減到 1，在 BIT 中找第 X_k+1 個空位。
2. LIS 遞推：按最終位置從左到右處理，dp[i] = 1 + max{dp[j] | j < i 且 val[j] < val[i]}。因值即插入順序 1..N，val 遞增，故 dp[i] = 1 + max{dp[j] | j < pos[i]} —— 即前綴最大值。
3. BIT 維護前綴最大值：插入位置 pos 時，查詢 [1, pos-1] 最大值 +1 即為當前 LIS 結尾長度，更新 pos 處值。

算法流程

1. 讀入 N 及 X[1..N]。
2. 求最終位置：BIT 初始全 1（表示空位）。對 k=N..1，二分查找第 X[k]+1 個 1 的位置 → pos[k]，並將該位置置 0。
3. 計算 LIS：新 BIT 存前綴最大值。對 k=1..N，cur = query(pos[k]-1) + 1，update(pos[k], cur)，輸出 max(ans, cur)。

C++ 關鍵代碼

const int MAXN = 100005;
int n, a[MAXN], pos[MAXN], bit[MAXN];

// BIT 基礎操作
int query(int x) { int r=0; for(;x;x-=x&-x) r+=bit[x]; return r; }
void add(int x) { for(;x<=n;x+=x&-x) bit[x]++; }

// 最大值 BIT
int queryMax(int x) { int r=0; for(;x;x-=x&-x) r=max(r,bit[x]); return r; }
void updateMax(int x,int v) { for(;x<=n;x+=x&-x) bit[x]=max(bit[x],v); }

int main() {
    n = read();
    for(int i=1;i<=n;i++) a[i]=read()+1; // X_k -> 1-based
    
    // 1. 逆向求最終位置
    memset(bit,0,sizeof(bit));
    for(int i=1;i<=n;i++) add(i); // 初始全空位
    for(int i=n;i>=1;i--) {
        int l=1, r=n, target=a[i];
        while(l= target) r=mid; // 空位數 = mid - 已佔用數
            else l=mid+1;
        }
        pos[i]=l;
        add(l); // 佔用該位置（實為更新BIT，標記非空）
        // 實際需將bit[l]從1改為0，此處用另一BIT或修改query邏輯
    }
    
    // 2. 正向算LIS
    memset(bit,0,sizeof(bit));
    int ans=0;
    for(int i=1;i<=n;i++) {
        int cur = queryMax(pos[i]-1) + 1;
        updateMax(pos[i], cur);
        ans = max(ans, cur);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 時間：O(N log N) —— 兩輪 BIT 操作，每輪 N 次 log N。
• 空間：O(N)。

關鍵細節

• 第一輪 BIT 求第 k 個空位：可用 query(mid) 返回 [1,mid] 已佔用數，空位數 = mid - query(mid)。
• 第二輪 BIT 維護前綴最大值：update 取 max，query 取前綴 max。
• 輸出每步的全局 LIS 長度（而非以當前元素結尾的長度）。