Codeforces 520D Cubes：集合維護可拆除立方體，雙人博弈貪心

題目大意

同 Codeforces 520D / 295 Div1 B Cubes。二維平面 n（≤10⁵）個立方體，穩定條件：y=0 或下方三鄰居至少一個存在。兩人輪流拆除：先手取最大編號，後手取最小編號，拆除過程保持穩定。求最終 n 進制數模 1e9+9。

算法優化：有序集合 + 延遲刪除

用 set 維護當前可拆除立方體編號（自動有序）。每輪：
- 先手：取 *set.rbegin()（最大）。
- 後手：取 *set.begin()（最小）。
取出後需二次驗證 can_remove（因集合中可能殘留已失效元素），若失效則擦除繼續取下一個。
拆除後從 map 刪除座標映射，檢查其下方三鄰居是否變為可拆除，若是插入集合。

核心代碼

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+9;
int n, x[100010], y[100010];
map<pair<int,int>, int> mp;
set cand;
bool vis[100010];

bool can_remove(int u) {
    int X = x[u], Y = y[u];
    // 檢查上方三鄰居 (X-1,Y+1), (X,Y+1), (X+1,Y+1)
    for (int dx = -1; dx <= 1; ++dx) {
        auto it = mp.find({X+dx, Y+1});
        if (it == mp.end() || vis[it->second]) continue;
        int v = it->second;
        // v 的下方三鄰居是否還有其他支撐
        bool supported = false;
        for (int dx2 = -1; dx2 <= 1; ++dx2) {
            if (dx2 == 0 && Y == y[v]) continue; // 排除自己? 實際檢查 v 的下方
            auto it2 = mp.find({x[v]+dx2, y[v]-1});
            if (it2 != mp.end() && !vis[it2->second]) { supported = true; break; }
        }
        if (!supported) return false;
    }
    return true;
}

void add_candidates(int u) {
    int X = x[u], Y = y[u];
    for (int dx = -1; dx <= 1; ++dx) {
        auto it = mp.find({X+dx, Y-1});
        if (it != mp.end() && !vis[it->second] && can_remove(it->second))
            cand.insert(it->second);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) { cin >> x[i] >> y[i]; mp[{x[i], y[i]}] = i; }
    for (int i = 0; i < n; ++i) if (can_remove(i)) cand.insert(i);
    long long ans = 0;
    for (int turn = 0; turn < n; ++turn) {
        int u = -1;
        if (turn % 2 == 0) { // Vasya 取大
            while (!cand.empty()) {
                int t = *cand.rbegin();
                if (vis[t] || !can_remove(t)) { cand.erase(t); continue; }
                u = t; cand.erase(t); break;
            }
        } else { // Petya 取小
            while (!cand.empty()) {
                int t = *cand.begin();
                if (vis[t] || !can_remove(t)) { cand.erase(t); continue; }
                u = t; cand.erase(t); break;
            }
        }
        vis[u] = true;
        ans = (ans * n + u) % MOD;
        mp.erase({x[u], y[u]});
        add_candidates(u);
    }
    cout << ans << '\n';
    return 0;
}

複雜度

• 每立方體進出集合 O(1) 次，can_remove 檢查 9 個鄰居 O(log n)（map 查找）。
• 總時間：O(n log n)。
• 空間：O(n)。

關鍵差異

相比優先隊列版本，set 直接支援取最大/最小且可高效刪除任意元素，避免了「殘留元素需反覆彈出」的開銷，代碼更簡潔。