Codeforces 520D / 295 Div1 B Cubes：優先隊列貪心模擬拆除順序

題目大意

二維平面上有 M（≤10⁵）個立方體，座標 (x, y)，y ≥ 0。立方體穩定條件：y = 0 或下方三個位置 (x-1, y-1), (x, y-1), (x+1, y-1) 至少有一個立方體。兩人輪流拆除：先手（Vasya）欲使最終 M 進制數最大，後手（Petya）欲最小。輸出最終數模 1e9+9。

核心觀察

一個立方體可被拆除，當且僅當拆除後，其上方三個位置 (x-1, y+1), (x, y+1), (x+1, y+1) 的立方體（若存在）仍保持穩定（即它們下方仍至少有一個支撐）。

算法流程

1. 預處理：用 map<pair<int,int>, int> 記錄座標→編號。
2. 判斷函數 can_remove(u)：檢查上方三鄰居是否仍有其他支撐。
3. 維護兩個優先隊列：qmax（大根堆，Vasya 取最大編號），qmin（小根堆，Petya 取最小編號）。初始將所有可拆除立方體加入兩隊列。
4. 輪流從對應隊列取堆頂，若已拆除或不可拆除則彈出繼續；否則拆除，記錄編號，從 map 刪除，檢查其下方三鄰居是否變為可拆除，若是則加入隊列。
5. 拆除序列構成 M 進制數，按順序計算 ans = (ans * M + id) % MOD。

關鍵代碼片段

bool can_remove(Point p) {
    for (int i = 3; i < 6; ++i) { // 上方三鄰居
        Point nb = {p.x + dx[i], p.y + dy[i]};
        auto it = mp.find(nb);
        if (it == mp.end()) continue;
        int v = it->second;
        if (vis[v]) continue;
        bool supported = false;
        for (int j = 0; j < 3; ++j) { // 該鄰居的下方三鄰居
            Point nb2 = {nb.x + dx[j], nb.y + dy[j]};
            if (nb2.x == p.x && nb2.y == p.y) continue;
            if (mp.count(nb2) && !vis[mp[nb2]]) { supported = true; break; }
        }
        if (!supported) return false;
    }
    return true;
}

// 主循環
int turn = -1;
vector<long long> seq;
while (true) {
    turn = (turn + 1) % 2;
    int u = -1;
    if (turn == 0) { // Vasya 取大
        while (!qmax.empty()) {
            int t = qmax.top();
            if (vis[t] || !can_remove(poi[t])) { qmax.pop(); continue; }
            u = t; qmax.pop(); break;
        }
    } else { // Petya 取小
        while (!qmin.empty()) {
            int t = qmin.top();
            if (vis[t] || !can_remove(poi[t])) { qmin.pop(); continue; }
            u = t; qmin.pop(); break;
        }
    }
    if (u == -1) break;
    vis[u] = true;
    seq.push_back(u);
    mp.erase({poi[u].x, poi[u].y});
    // 檢查下方三鄰居
    for (int i = 0; i < 3; ++i) {
        Point nb = {poi[u].x + dx[i], poi[u].y + dy[i]};
        auto it = mp.find(nb);
        if (it != mp.end() && !vis[it->second] && can_remove(poi[it->second])) {
            qmax.push(it->second);
            qmin.push(it->second);
        }
    }
}

複雜度

• 每個立方體進出隊列常數次，can_remove 檢查 3×3 = 9 個鄰居，均為 O(1)（map 查找 O(log M)）。
• 總時間：O(M log M)。
• 空間：O(M)。

注意事項

• 隊列中可能殘留已拆除或不可拆除的元素，取出時需二次驗證。
• 使用 map 而非 unordered_map 避免 hack，或自定義哈希。
• 模數 1e9+9，快速冪計算最終答案。