Overview

After processing all rectangular region flip operations on the lighting panel, for each query we need to find “the number of lit cells within the region” and “the number of islands completely contained within the region.”

The flip operations are processed collectively using a 2D imos method, and the islands are computed only once on the final state.

Analysis

First, each operation flips all cells within a rectangle.

Naively updating all target cells for each operation would take \(O(NHW)\) in the worst case, which is too slow.

The key insight is that for each cell, all we need is the parity of “how many times it was flipped.”

• If flipped an even number of times → off
• If flipped an odd number of times → on

Therefore, by using the 2D imos method, which can efficiently process rectangular additions, we can determine the state after all operations in \(O(N + HW)\).

---

Next, each query asks for the number of lit cells within a region.

Once the final state is known, we can build a 2D prefix sum where lit cells are \(1\) and unlit cells are \(0\), allowing us to answer each query in \(O(1)\).

---

On the other hand, we need to be careful about counting islands.

As stated in the problem, islands are connected components in the “final state of the entire panel.”
We must not recompute connected components only within the query region.

For example, if only part of an island falls within the query region, that island cannot be considered “completely contained.”

Therefore, we perform BFS/DFS only once on the entire final state and examine the extent of each island.

Whether an island is completely contained within a rectangular region \([P,Q] \times [R,S]\) can be determined using the top, bottom, left, and right extents of the island.

For an island, let:

• \(\mathrm{minr}\) be the minimum row
• \(\mathrm{maxr}\) be the maximum row
• \(\mathrm{minc}\) be the minimum column
• \(\mathrm{maxc}\) be the maximum column

Then, the condition for the island to be completely contained within the query region is:

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

In other words, it suffices to record the bounding rectangle for each island.

Algorithm

1. Determine the final state using the 2D imos method

For each operation \((A_i, B_i, C_i, D_i)\), add the following to the difference array diff:

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

Then, by computing the 2D prefix sum from top to bottom, we obtain the number of times each cell was flipped.

Since a cell is lit if the flip count is odd:

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

---

2. Build a 2D prefix sum for counting lit cells

Create a prefix sum ps where lit cells are \(1\) and unlit cells are \(0\).

Then, the number of lit cells within the query region \([P,Q] \times [R,S]\) is:

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

---

3. Enumerate islands using BFS

For lit cells in the final state, perform BFS starting from any unvisited cell.

While visiting all cells belonging to the same island via BFS, update the island’s:

• Minimum row
• Maximum row
• Minimum column
• Maximum column

After the BFS completes, save the bounding rectangle of that island.

---

4. Answer each query

For each query, first compute the number of lit cells in \(O(1)\) using the 2D prefix sum.

Next, check for all saved islands whether their bounding rectangle is completely contained within the query region.

The condition is as follows:

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

The number of islands satisfying this condition is the second answer to the query.

Complexity

• Time complexity: \(O(N + HW + M \times K)\)
  • \(K\) is the number of islands
  • Since \(K \leq HW\), the worst case is \(O(N + HW + MHW)\)
  • This is fast enough because of the constraint \(M \times H \times W \leq 5 \times 10^7\)
• Space complexity: \(O(HW)\)

Implementation Notes

• Using \(1\)-indexed arrays makes the prefix sum formulas easier to understand.

• In the 2D imos method, since \(B+1\) and \(D+1\) are used, allocate array sizes of at least H + 2 and W + 2.

• Recomputing the number of islands via BFS for each query not only risks misdefining islands but also increases the computational complexity. Islands should be computed only once on the entire final state.

• In BFS, forgetting to manage visited status will cause the same cell to be processed multiple times.

• To determine whether an island is completely contained within a query region, it suffices to use only the bounding rectangle — there is no need to store all cells of the island.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.