概要

\(H \times W\) のマス目に対して \(N\) 回の長方形領域の反転操作を行い、最終的な点灯状態における \(M\) 個のクエリに答える問題です。各クエリでは、指定された領域内の「点灯マスの個数」と、その領域に「完全に収まっている島の個数」を求めます。

考察

この問題を解くためには、大きく分けて以下の3つのステップが必要です。

1. 最終的なパネルの状態を求める 各操作は「範囲内の 0 と 1 を反転させる」というものです。これは、各マスが「何回の操作に含まれたか」の偶奇（XOR）を求めることと同じです。 素朴に \(N\) 回の操作を毎回全マスに対して行うと \(O(N \times H \times W)\) かかり間に合いませんが、2次元のいもす法（XOR版）を用いることで \(O(H \times W + N)\) で計算可能です。

2. 「島」を特定し、その範囲を記録する 「島」は最終状態における連結成分です。全マスを走査し、点灯しているマスを見つけたら BFS（幅優先探索）や DFS（深さ優先探索）を行うことで島を特定できます。 ここで重要なのは、ある島がクエリの領域 \([P, Q] \times [R, S]\) に完全に収まっている条件を考えることです。島に属するすべてのマス \((r, c)\) が \(P \le r \le Q\) かつ \(R \le c \le S\) を満たす必要があります。 これは、各島について最小の行番号、最大の行番号、最小の列番号、最大の列番号（外接長方形、Bounding Box）をあらかじめ記録しておけば、その 4 値がクエリの範囲内に収まっているかを判定するだけで済みます。

3. クエリに効率よく答える

   • 点灯マスの個数: 2次元累積和を用いることで、各クエリ \(O(1)\) で計算できます。
   • 完全に収まっている島の個数: 各クエリに対して、すべての島を走査して判定します。島の総数を \(K\) とすると、クエリ全体で \(O(M \times K)\) となります。 制約の \(M \times H \times W \leq 5 \times 10^7\) という特殊な条件は、この \(O(M \times K)\) の計算が間に合うことを示唆しています（島の数 \(K\) は最大でも \((H \times W)/2\) 程度であるため）。

アルゴリズム

1. 状態の復元: 2次元配列 diff を用意し、操作 \((A_i, B_i, C_i, D_i)\) に対して、(A_i, C_i), (A_i, D_i+1), (B_i+1, C_i), (B_i+1, D_i+1) の 4 箇所に \(1\) を XOR します。その後、2次元累積 XOR を取ることで、最終的な各マスの状態 grid[i][j] を得ます。
2. 累積和の計算: grid[i][j] を元に、点灯マスの個数に関する2次元累積和 pref[i][j] を計算します。
3. 島の抽出: 未訪問の点灯マスから BFS を開始し、連結成分（島）を探索します。探索中に、その島に属するマスの行・列の最小値と最大値を更新し、BBox（外接長方形）として保存します。
4. 回答: 各クエリ \((P, Q, R, S)\) について：
   • 点灯マス数 = pref[Q][S] - pref[P-1][S] - pref[Q][R-1] + pref[P-1][R-1]
   • 島の判定 = 各島の BBox が \(P \le minR, maxR \le Q\) かつ \(R \le minC, maxC \le S\) を満たすか確認。

計算量

• 時間計算量: \(O(H \times W + N + M \times K)\)
  • \(K\) は島の数（最大 \(H \times W / 2\)）。
  • 制約より \(M \times K \approx 2.5 \times 10^7\) 程度となり、実行時間制限内に収まります。
• 空間計算量: \(O(H \times W)\)
  • グリッドの状態や累積和を保持するために必要です。

実装のポイント

• 2次元いもす法: XOR を使うことで、反転操作を簡潔に処理できます。

• BFS の高速化: std::vector をキューとして使い、reserve でメモリを確保しておくことで、動的なメモリ割り当てのオーバーヘッドを減らせます。

• 境界条件: 累積和やいもす法で範囲外参照を起こさないよう、配列サイズを \((H+2) \times (W+2)\) 程度に確保しておくと安全です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Lighting Panels and Picture Frames
 * The task is to determine the final state of a lighting panel after N flip operations
 * and answer M queries. Each query asks for the number of ON cells in a rectangular region
 * and the number of islands (connected components of ON cells) completely contained in it.
 *
 * Complexity Analysis:
 * 1. Determining the final grid state: O(H * W + N) using a 2D XOR difference array.
 * 2. Finding islands and their bounding boxes: O(H * W) using BFS.
 * 3. Precomputing 2D prefix sums for ON cells: O(H * W).
 * 4. Answering M queries:
 *    - Query 1 (ON cells): O(1) using 2D prefix sums.
 *    - Query 2 (contained islands): O(K) per query, where K is the number of islands.
 *    Total for queries: O(M * K).
 *
 * Given K <= (H * W + 1) / 2 and the constraint M * H * W <= 5 * 10^7,
 * the overall complexity is approximately O(H * W + N + M * K), which is roughly
 * 2.5 * 10^7 operations in the worst case, fitting well within the 2s time limit.
 */

struct BBox {
    int minR, maxR, minC, maxC;
};

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, N;
    if (!(cin >> H >> W >> N)) return 0;

    // 2D XOR difference array to handle rectangular flip operations efficiently.
    // Using H+2 and W+2 to avoid boundary checks.
    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] ^= 1;
        diff[a][d + 1] ^= 1;
        diff[b + 1][c] ^= 1;
        diff[b + 1][d + 1] ^= 1;
    }

    // Compute the final grid state and precompute 2D prefix sums for ON cells.
    vector<vector<int>> grid(H + 1, vector<int>(W + 1, 0));
    vector<vector<int>> pref(H + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            // XOR prefix sum to get the flip state of each cell.
            grid[i][j] = diff[i][j] ^ grid[i - 1][j] ^ grid[i][j - 1] ^ grid[i - 1][j - 1];
            // Standard prefix sum to count ON cells in O(1).
            pref[i][j] = grid[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    // Identify all islands and their bounding boxes using BFS.
    vector<vector<bool>> visited(H + 1, vector<bool>(W + 1, false));
    vector<BBox> islands;
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};

    vector<pair<int, int>> bfs_q;
    bfs_q.reserve(H * W);

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (grid[i][j] && !visited[i][j]) {
                bfs_q.clear();
                bfs_q.push_back({i, j});
                visited[i][j] = true;
                int minR = i, maxR = i, minC = j, maxC = j;
                int head = 0;
                while (head < (int)bfs_q.size()) {
                    pair<int, int> curr = bfs_q[head++];
                    int r = curr.first;
                    int c = curr.second;
                    if (r < minR) minR = r;
                    if (r > maxR) maxR = r;
                    if (c < minC) minC = c;
                    if (c > maxC) maxC = c;
                    for (int d = 0; d < 4; ++d) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];
                        if (nr >= 1 && nr <= H && nc >= 1 && nc <= W && grid[nr][nc] && !visited[nr][nc]) {
                            visited[nr][nc] = true;
                            bfs_q.push_back({nr, nc});
                        }
                    }
                }
                islands.push_back({minR, maxR, minC, maxC});
            }
        }
    }

    // Answer M queries.
    int M;
    if (!(cin >> M)) return 0;
    while (M--) {
        int P, Q, R, S;
        cin >> P >> Q >> R >> S;
        // Query 1: Count ON cells in the rectangle [P, Q] x [R, S].
        int count1 = pref[Q][S] - pref[P - 1][S] - pref[Q][R - 1] + pref[P - 1][R - 1];
        // Query 2: Count islands completely contained within [P, Q] x [R, S].
        // An island is contained if its bounding box is within the query rectangle.
        int count2 = 0;
        for (const auto& island : islands) {
            if (island.minR >= P && island.maxR <= Q && island.minC >= R && island.maxC <= S) {
                count2++;
            }
        }
        cout << count1 << " " << count2 << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。