問題概要

$H \times W$ のグリッドがあり、最初は各マスに壁がある。このグリッドに次の $Q$ 回のクエリを実行したあとの、残っている壁の個数を求めよ。

【クエリ】
マス $(r, c)$ のある位置に爆弾を落とす。

もしこのマスに壁があるなら、その壁を破壊する
壁がないならば、そのマスから上下左右それぞれの方向について、直近の壁を破壊する

制約

$H \times W \le 4 \times 10^{5}$
$1 \times Q \times 2 \times 10^{5}$

考えたこと

たとえば壁のないマス $(r, c)$ に落とした爆弾の左右方向の壁について考えよう。このとき、

右側：行 $r$ に残っている壁のある列番号のうち、 $c$ 以上の最小のものを求め、それを削除する
左側：上記の列番号の前の列番号について削除する

という処理を実行することになる。上下方向も同様である。ここで分かるのは「lower_bound()」と「削除」の操作が必要となることである。このような処理は set を用いるに限る。

左右方向と上下方向のクエリに対応するために、次のようなデータ構造を用意しておこう。

rows[r] ← 行 $r$ に残っている壁のある列番号の集合
cols[c] ← 列 $c$ に残っている壁のある行番号の集合

このデータ構造を初期化するのには $O(HW(\log H + \log W))$ の計算量を要する。制約をよくみると $H, W \le 4 \times 10^{5}$ ではなく $H \times W \le 4 \times 10^{5}$ なので、大丈夫だ。

あとは、毎回のクエリに対して、上記のデータ構造を着実に更新していけばよい。具体的な処理は次のコードを参照。

全体の計算量は $O(HW + Q)(\log H + \log W))$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W, Q;
    cin >> H >> W >> Q;
    vector<set<int>> rows(H, {-1, W}), cols(W, {-1, H});
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        rows[i].insert(j);
        cols[j].insert(i);
    }

    auto del = [&](int r, int c) -> void {
        if (r < 0 || r >= H || c < 0 || c >= W) return;
        rows[r].erase(c);
        cols[c].erase(r);
    };

    for (int _ = 0; _ < Q; _++) {
        int r, c;
        cin >> r >> c;
        --r, --c;

        // (r, c) に壁があるとき
        auto right = rows[r].lower_bound(c);
        if (*right == c) {
            del(r, *right);
            continue;
        }

        // (r, c) に壁がないとき
        auto left = prev(right);
        auto down = cols[c].lower_bound(r);
        auto top = prev(down);
        del(r, *right), del(r, *left), del(*down, c), del(*top, c);
    }

    long long res = 0;
    for (int r = 0; r < H; r++) res += (long long)rows[r].size() - 2;
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 370 D - Cross Explosion (1Q, 緑色, 400 点)

問題概要

制約

考えたこと

コード