実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1088

問題概要

縦 $H$ マス、横 $W$ マスのグリッドがあり、上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表す。はじめ、すべてのマスに壁が1個ずつ立てられている。以下の形式のクエリを $Q$ 個処理した後に残っている壁の数を求めよ。

クエリ : 番目のクエリでは整数が与えられ、に爆弾を置いて壁を爆破することを考える。
- $(R_q, C_q)$ に壁が存在するとき、その壁を破壊する。
- $(R_q, C_q)$ に壁が存在しないとき、 $(R_q, C_q)$ から上下左右それぞれを見て最初に現れる壁を破壊する。

制約

入力はすべて整数。
$1 \leq H, W$
$H \times W \leq 4 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq R_q \leq H$
$1 \leq C_q \leq W$

考察

まずはグリッド上の各マスの壁の有無を単純な二次元bool配列で管理して愚直に実装する方針をとってみよう。フラグが立っているなら壁があることを意味する。

各クエリの処理は以下のようになる。

$(R_q, C_q)$ に壁が存在するとき、 $(R_q, C_q)$ のフラグを消す (壁を破壊) 。
$(R_q, C_q)$ に壁が存在しないとき、上下左右方向に $(R_q, C_q)$ から1マスずつ壁があるまで探索する。壁が存在したらそれを破壊して終了。

しかし、このアルゴリズムでは計算量が $O(Q + HW)(H + W)$ となってしまい、実行時間制限に微妙に間に合わない。

上のアルゴリズムで無駄そうなのが、「 $(R_q, C_q)$ に壁が存在しないとき、上下左右方向に1マスずつ探索する」という部分だ。これをどうにかして効率化したい。

ここで、線形探索を二分探索で高速化する (イメージとしては、各方向に対して壁を破壊したマスとそうでないマスの境界を一発で求める感じ) ことを考える。これは、各行・列のマスでまだ壁が破壊されていないマスを順序付き集合 (C++ でいうset) に格納し、これに対して二分探索を行うことで実現できる。

具体的な実装についてはコードの方を参照してほしい。特にポインタの扱いは少々特殊なので、注意して実装していきたい。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int H, W, Q;
    cin >> H >> W >> Q;

    vector<set<int>> rows(H), cols(W);
    rep(i, 0, H) rep(j, 0, W) rows[i].insert(j), cols[j].insert(i);

    int remain = H * W;
    while (Q--)
    {
        int R, C;
        cin >> R >> C;
        R--, C--;

        if (rows[R].contains(C)) {
            rows[R].erase(C);
            cols[C].erase(R);
            
            remain--;

            continue;
        }

        auto itr = cols[C].lower_bound(R);
        if (itr != cols[C].begin()) {
            rows[*prev(itr)].erase(C);
            cols[C].erase(prev(itr));

            remain--;
        }
        if (itr != cols[C].end()) {
            rows[*itr].erase(C);
            cols[C].erase(itr);

            remain--;
        }

        itr = rows[R].lower_bound(C);
        if (itr != rows[R].begin()) {
            cols[*prev(itr)].erase(R);
            rows[R].erase(prev(itr));

            remain--;
        }
        if (itr != rows[R].end()) {
            cols[*itr].erase(R);
            rows[R].erase(itr);

            remain--;
        }
    }
    
    cout << remain << endl;
}