UVA 1471 Defense Lines：刪除子段後最長上升子序列的集合優化

問題描述

給定長度 n (≤ 200,000) 的序列，刪除一段連續子序列，使剩餘兩段拼接後的最長連續上升子序列（LCIS）長度最大。輸出該最大長度。

預處理：前綴/後綴 LCIS 長度

• f[i]：以 i 為結尾的連續上升子序列長度
• g[i]：以 i 為開頭的連續上升子序列長度

f[1] = 1;
for (i=2..n) f[i] = (a[i] > a[i-1]) ? f[i-1]+1 : 1;
g[n] = 1;
for (i=n-1..1) g[i] = (a[i] < a[i+1]) ? g[i+1]+1 : 1;

暴力枚舉優化：從 O(n²) 到 O(n log n)

枚舉刪除區間 [i+1, j-1]，剩餘拼接點為 i 和 j。需 a[i] < a[j] 才能連接。目標：

max_{i < j, a[i] < a[j]} (f[i] + g[j])

核心優化：掃描線 + 有序集合

按 j 從左到右掃描，維護「候選 i」的集合。關鍵觀察：若 i1 < i2 且 a[i1] ≤ a[i2] 且 f[i1] ≥ f[i2]，則 i2 永遠不可能是最優解（被 i1 支配）。

維護一個 `set>`，按 `a[i]` 排序，存儲「非被支配」的 (a[i], f[i])。操作：

1. 查詢：`lower_bound(a[j])` 找到第一個 ≥ a[j] 的元素，其前驅即為最大的 < a[j] 的候選
2. 插入：加入 (a[j], g[j]) 前，刪除所有被它支配的元素（a 值更大且 f 值不更大）

完整代碼

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
int a[MAXN], f[MAXN], g[MAXN];
int n;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        
        g[1] = 1;
        for (int i = 2; i <= n; ++i)
            g[i] = (a[i] > a[i-1]) ? g[i-1] + 1 : 1;
        f[n] = 1;
        for (int i = n-1; i >= 1; --i)
            f[i] = (a[i] < a[i+1]) ? f[i+1] + 1 : 1;
        
        set> s;  // (a[i], g[i])
        s.insert({a[1], g[1]});
        int ans = 1;
        
        for (int i = 2; i <= n; ++i) {
            pair cur = {a[i], g[i]};
            auto it = s.lower_bound(cur);
            
            // 查詢最佳前驅
            if (it != s.begin()) {
                auto prev = *prev(it);
                ans = max(ans, f[i] + prev.second);
                // 若前驅 g 值 ≥ 當前，當前被支配，無需插入
                if (prev.second >= cur.second) continue;
            }
            
            // 插入並清理被支配元素
            s.erase(cur);  // 確保唯一
            s.insert(cur);
            it = s.find(cur);
            ++it;
            while (it != s.end() && it->first > cur.first && it->second <= cur.second) {
                it = s.erase(it);  // 刪除並獲取下一個迭代器
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵技術點

1. 支配關係：(a1, f1) 支配 (a2, f2) ⟺ a1 ≤ a2 且 f1 ≥ f2
2. set 有序性：自動按 a 值排序，支持 O(log n) 查詢/插入/刪除
3. 迭代器安全刪除：`it = s.erase(it)` 返回下一個有效迭代器
4. 雙向受益：f[i] 來自右側，g[i] 來自左側，掃描方向對應

複雜度

• 預處理：O(n)
• 掃描：每個元素進出 set 各一次，O(n log n)
• 總體：O(n log n)，完美應對 n=200,000