HDU 4022 - Bombing：STL multiset 模擬坐標轟炸

問題

平面上 n 個點，m 次操作：

• u=0, v：轟炸 x=v 縱線上所有點，輸出被炸數量
• u=1, v：轟炸 y=v 橫線上所有點，輸出被炸數量

被炸點從集合中移除。n,m ≤ 10000。

資料結構：雙向索引

• map cntX, cntY：統計每條縱/橫線點數
• multiset setX：按 x 後 y 排序
• multiset setY：按 y 後 x 排序
• 雙向指針：炸 x 線時，在 setX 中 lower_bound 找到範圍，逐個刪除並同步刪除 setY 中對應點，更新計數

關鍵代碼

struct X { int x,y; bool operator<(X o) const { return x!=o.x? x sx; multiset sy;
map cx, cy;

void bombX(int v) {
    if (!cx.count(v)) { puts("0"); return; }
    printf("%d\n", cx[v]);
    cx.erase(v);
    auto it = sx.lower_bound({v, -INF});
    while (it != sx.end() && it->x == v) {
        int y = it->y;
        sy.erase(sy.find({v, y}));
        if (--cy[y] == 0) cy.erase(y);
        auto tmp = it++;
        sx.erase(tmp);
    }
}

複雜度

• 每點被刪除一次，multiset 操作 O(log n)
• 總 O((n+m) log n)