概要

長方形領域の反転操作をすべて処理した後の照明パネルについて、各質問ごとに「領域内の点灯マス数」と「領域内に完全に収まる島の数」を求める問題です。

反転操作は二次元いもす法でまとめて処理し、島は最終状態全体で一度だけ求めておきます。

考察

まず、各操作で長方形内のすべてのマスを反転します。

素朴に各操作ごとに対象マスをすべて更新すると、最悪で \(O(NHW)\) かかってしまい、間に合いません。

ここで重要なのは、各マスについて必要なのは「何回反転されたか」の偶奇だけだという点です。

• 反転回数が偶数回なら消灯
• 反転回数が奇数回なら点灯

したがって、長方形加算を高速に処理できる二次元いもす法を使えば、すべての操作後の状態を \(O(N + HW)\) で求められます。

---

次に、質問では領域内の点灯マス数を求めます。

これは最終状態が分かっていれば、点灯しているマスを \(1\)、消灯しているマスを \(0\) とした二次元累積和を作ることで、各質問に \(O(1)\) で答えられます。

---

一方で、島の数について注意が必要です。

問題文にある通り、島は「パネル全体の最終状態」における連結成分です。
質問領域の中だけで連結成分を作り直してはいけません。

例えば、ある島の一部だけが質問領域に入っている場合、その島は「完全に収まっている」とは言えません。

そこで、最終状態全体に対して一度だけ BFS/DFS を行い、各島の範囲を調べます。

ある島が長方形領域 \([P,Q] \times [R,S]\) に完全に収まっているかどうかは、その島の上下左右の端を使って判定できます。

島について、

• 最小行を \(\mathrm{minr}\)
• 最大行を \(\mathrm{maxr}\)
• 最小列を \(\mathrm{minc}\)
• 最大列を \(\mathrm{maxc}\)

とすると、その島が質問領域に完全に収まる条件は

\[ P \leq \mathrm{minr}, \quad \mathrm{maxr} \leq Q, \quad R \leq \mathrm{minc}, \quad \mathrm{maxc} \leq S \]

です。

つまり、各島について外接長方形を記録しておけば十分です。

アルゴリズム

1. 二次元いもす法で最終状態を求める

各操作 \((A_i, B_i, C_i, D_i)\) に対して、差分配列 diff に以下を加えます。

diff[A][C] += 1
diff[B+1][C] -= 1
diff[A][D+1] -= 1
diff[B+1][D+1] += 1

その後、上から順に二次元累積和を取ると、各マスが何回反転されたかが分かります。

反転回数が奇数なら点灯なので、

lit[r][c] = diff[r][c] & 1;

とします。

---

2. 点灯マス数用の二次元累積和を作る

点灯しているマスを \(1\)、消灯しているマスを \(0\) として累積和 ps を作ります。

すると、質問領域 \([P,Q] \times [R,S]\) に含まれる点灯マス数は

\[ ps[Q][S] - ps[P-1][S] - ps[Q][R-1] + ps[P-1][R-1] \]

で求められます。

---

3. BFS で島を列挙する

最終状態の点灯マスについて、まだ訪れていないマスから BFS を行います。

BFS で同じ島に属するマスをすべて訪問しながら、その島の

• 最小行
• 最大行
• 最小列
• 最大列

を更新します。

BFS が終わったら、その島の外接長方形を保存します。

---

4. 各質問に答える

各質問について、まず二次元累積和から点灯マス数を \(O(1)\) で求めます。

次に、保存しておいたすべての島について、その外接長方形が質問領域に完全に含まれるかを調べます。

条件は次の通りです。

P <= minr && maxr <= Q && R <= minc && maxc <= S

この条件を満たす島の個数が、質問への 2 つ目の答えになります。

計算量

• 時間計算量: \(O(N + HW + M \times K)\)
  • \(K\) は島の個数です
  • \(K \leq HW\) なので、最悪では \(O(N + HW + MHW)\) です
  • 制約に \(M \times H \times W \leq 5 \times 10^7\) があるため間に合います
• 空間計算量: \(O(HW)\)

実装のポイント

• 配列は \(1\)-indexed で扱うと、累積和の式が分かりやすくなります。

• 二次元いもす法では \(B+1\) や \(D+1\) を使うため、配列サイズは H + 2, W + 2 程度確保しておきます。

• 島の個数を質問ごとに BFS で求め直すと、島の定義を間違えるだけでなく計算量も大きくなります。島は最終状態全体で一度だけ求めます。

• BFS では、訪問済み管理を忘れると同じマスを何度も処理してしまいます。

• 島が質問領域内に完全に収まるかどうかは、島の全マスを保存しなくても、外接長方形だけで判定できます。

  ソースコード

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

struct Box {
    int minr, maxr, minc, maxc;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, N;
    cin >> H >> W >> N;

    vector<vector<int>> diff(H + 2, vector<int>(W + 2, 0));

    for (int i = 0; i < N; i++) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        diff[A][C]++;
        diff[B + 1][C]--;
        diff[A][D + 1]--;
        diff[B + 1][D + 1]++;
    }

    vector<vector<unsigned char>> lit(H + 1, vector<unsigned char>(W + 1, 0));
    vector<vector<int>> ps(H + 1, vector<int>(W + 1, 0));

    for (int r = 1; r <= H; r++) {
        for (int c = 1; c <= W; c++) {
            diff[r][c] += diff[r - 1][c] + diff[r][c - 1] - diff[r - 1][c - 1];
            lit[r][c] = diff[r][c] & 1;
            ps[r][c] = ps[r - 1][c] + ps[r][c - 1] - ps[r - 1][c - 1] + lit[r][c];
        }
    }

    vector<vector<unsigned char>> visited(H + 1, vector<unsigned char>(W + 1, 0));
    vector<Box> islands;
    islands.reserve((H * W + 1) / 2);

    vector<int> que;
    que.reserve(H * W);

    for (int sr = 1; sr <= H; sr++) {
        for (int sc = 1; sc <= W; sc++) {
            if (!lit[sr][sc] || visited[sr][sc]) continue;

            int minr = sr, maxr = sr, minc = sc, maxc = sc;
            que.clear();

            visited[sr][sc] = 1;
            que.push_back((sr - 1) * W + (sc - 1));

            for (size_t head = 0; head < que.size(); head++) {
                int idx = que[head];
                int r = idx / W + 1;
                int c = idx % W + 1;

                minr = min(minr, r);
                maxr = max(maxr, r);
                minc = min(minc, c);
                maxc = max(maxc, c);

                if (r > 1 && lit[r - 1][c] && !visited[r - 1][c]) {
                    visited[r - 1][c] = 1;
                    que.push_back((r - 2) * W + (c - 1));
                }
                if (r < H && lit[r + 1][c] && !visited[r + 1][c]) {
                    visited[r + 1][c] = 1;
                    que.push_back(r * W + (c - 1));
                }
                if (c > 1 && lit[r][c - 1] && !visited[r][c - 1]) {
                    visited[r][c - 1] = 1;
                    que.push_back((r - 1) * W + (c - 2));
                }
                if (c < W && lit[r][c + 1] && !visited[r][c + 1]) {
                    visited[r][c + 1] = 1;
                    que.push_back((r - 1) * W + c);
                }
            }

            islands.push_back({minr, maxr, minc, maxc});
        }
    }

    int M;
    cin >> M;

    while (M--) {
        int P, Q, R, S;
        cin >> P >> Q >> R >> S;

        int lit_count = ps[Q][S] - ps[P - 1][S] - ps[Q][R - 1] + ps[P - 1][R - 1];

        int island_count = 0;
        for (const auto& b : islands) {
            if (P <= b.minr && b.maxr <= Q && R <= b.minc && b.maxc <= S) {
                island_count++;
            }
        }

        cout << lit_count << ' ' << island_count << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。