Codeforces 387E：集合區間最小值查詢與有序集合優化

Codeforces 387E 要求從數列中刪除指定元素，每次刪除代價為當前區間長度，求最小總代價。本文解析「逆向思維 + 有序集合維護區間」的核心解法：按值從小到大加入，用 set 維護已加入位置，線段樹查詢區間長度。

問題重述

• 初始數列 1..n 的排列。
• 需刪除 k 個指定值，其餘 n-k 個保留。
• 刪除順序：每次選擇一個保留值，代價 = 其所在連續保留區間長度。
• 目標：最小化總代價。

關鍵洞察：逆向過程 + 貪心

1. 逆向思維：考慮從空集合開始，按值從小到大加入保留元素。加入時，該元素連接左右相鄰的已加入區間，新區間長度即為正向過程中刪除該元素的代價。
2. 貪心最優性：總是先刪除/加入最小值最優。因為小值不會為大值提供額外代價減免，反而可能增加大值的區間長度。

算法流程

1. 標記需保留的值（未被刪除）。
2. 按值 1..n 遍歷：
3. 若值需保留：將其位置插入有序集合 set<int> S。
4. 若值需刪除：在 S 中用 upper_bound 找到其左右鄰近的已保留位置，確定區間 [L, R]。
5. 用線段樹查詢區間 [L, R] 當前長度（即已保留元素數），累加到答案。
6. 在線段樹中將該位置標記為「已刪除」（長度 -1）。

數據結構

• pos[val]：值 val 在原數列中的位置。
• set<int> S：已加入保留元素的位置集合，支持 O(log n) 前驅/後繼查詢。
• 線段樹：維護區間內「保留元素計數」，支持單點更新、區間求和。

關鍵代碼片段（C++）

// 初始化線段樹：所有位置為1（初始全保留）
build(1, 1, n);

set<int> S;
S.insert(0); S.insert(n+1); // 哨兵

long long ans = 0;
for (int val = 1; val <= n; ++val) {
    if (toDelete[val]) {
        int p = pos[val];
        auto itR = S.upper_bound(p);
        int R = *itR - 1;
        int L = *(--itR) + 1;
        ans += query(1, 1, n, L, R); // 區間長度
        update(1, 1, n, p, 0);       // 標記刪除
    } else {
        S.insert(pos[val]); // 保留元素加入集合
    }
}
printf("%lld\n", ans);

複雜度分析

• 遍歷 n 個值：O(n)
• set 操作：O(log n) 每次
• 線段樹查詢/更新：O(log n) 每次
• 總時間：O(n log n)
• 空間：O(n)

總結

本題展示了「逆向構造 + 有序集合定位區間 + 線段樹維護動態統計」的經典組合。核心技巧：

1. 將「刪除代價 = 區間長度」轉化為「加入時合併區間長度」。
2. 用 set.upper_bound O(log n) 找到區間邊界。
3. 線段樹動態維護區間內有效元素計數。

此模式廣泛適用於「動態區間統計 + 离線處理」問題。