Overview

In an \(H \times W\) grid, given \(Q\) operations where pressing a switch at a specified cell toggles the light bulbs at that cell and its four adjacent cells (up, down, left, right), find the final state of the light bulbs at each cell (on: 1, off: 0).

Analysis

1. Key Properties of Operations

The toggle operation on the light bulbs has the following important properties: - Toggling an even number of times returns to the original state: Toggling a light bulb twice returns it to its original state. Therefore, what affects the final state is only whether the number of toggles is odd or even (its parity). - The order of operations does not affect the outcome: Regardless of the order in which the switches are pressed, the total number of times each cell is toggled remains the same.

2. Focusing on the Parity of Switch Presses

Pressing the switch at the same cell twice is equivalent to pressing it 0 times (not pressing it at all). Therefore, for each cell \((i, j)\), it is sufficient to record only whether its switch was ultimately pressed an odd or even number of times.

3. Condition for a Light Bulb to Toggle

Only the following switches affect the light bulb at cell \((i, j)\): - The switch at cell \((i, j)\) itself - The switches at cells adjacent to cell \((i, j)\) (up, down, left, right)

Therefore, whether the light bulb at cell \((i, j)\) is ultimately toggled depends on whether the total number of cells—among itself and its adjacent neighbors—whose switches were pressed an odd number of times is odd or even.

[Concrete Example] For cell \((i, j)\): - Its own switch was pressed 1 time. - The switch above was pressed 1 time. - The switch to the right was pressed 2 times (effectively 0 times). - The switches to the left and below were not pressed (0 times).

In this case, the total number of switch presses affecting cell \((i, j)\) is \(1 + 1 + 0 + 0 + 0 = 2\) (an even number). Since it is toggled an even number of times, the state of the light bulb at cell \((i, j)\) does not change from its initial state.

Algorithm

1. Record Switch Presses:
   • Prepare an \(H \times W\) array pressed initialized to all \(0\)s.
   • For each of the \(Q\) queries \((R_k, C_k)\), toggle the value of pressed[R_k][C_k] (flip between 0 and 1, i.e., XOR with 1).
2. Compute Final States:
   • For each cell \((i, j)\), compute the XOR sum (parity of the sum) of pressed values for itself and its adjacent neighbors \((ni, nj)\) (up, down, left, right).
   • If the XOR sum is \(1\) (an odd number of times), flip the character in the initial state \(S_i[j]\) (0 to 1, or 1 to 0).
3. Output the Result:
   • Output the updated strings \(S\) in order.

Complexity

• Time Complexity: \(O(HW + Q)\)
  • Query processing: Updating the parity of switch presses for each query takes \(O(1)\), totaling \(O(Q)\).
  • Computing final states: For all \(H \times W\) cells, checking at most 4 adjacent directions takes \(O(HW)\).
  • Given the constraints \(HW \le 10^6\) and \(Q \le 10^5\), this comfortably runs well within the time limit.
• Space Complexity: \(O(HW)\)
  • Uses \(O(HW)\) memory to store the grid light bulb states \(S\) and the switch press states pressed.

Implementation Details

• Converting to 0-indexed: The input in the problem is given 1-indexed (\(1 \leq R_k \leq H\), \(1 \leq C_k \leq W\)). Subtracting \(1\) upon receiving them to convert to 0-indexed makes it easier to prevent out-of-bounds array access.

• Using Direction Arrays: Storing the displacements for up, down, left, and right in arrays like dr = {0, 0, 1, -1} and dc = {1, -1, 0, 0} allows you to cleanly implement adjacent cell traversal using a loop.

• Fast I/O: Since the input and output sizes are large with \(H \times W \leq 10^6\), in C++, speed up I/O by using cin.tie(nullptr); ios::sync_with_stdio(false); and using \n instead of endl for newlines.

  Source Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

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

    vector<string> S(H);
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }

    int Q;
    cin >> Q;

    vector<vector<int>> pressed(H, vector<int>(W, 0));
    for (int k = 0; k < Q; ++k) {
        int r, c;
        cin >> r >> c;
        --r; --c;
        pressed[r][c] ^= 1;
    }

    const int dr[] = {0, 0, 1, -1};
    const int dc[] = {1, -1, 0, 0};

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int flips = pressed[i][j];
            for (int d = 0; d < 4; ++d) {
                int ni = i + dr[d];
                int nj = j + dc[d];
                if (0 <= ni && ni < H && 0 <= nj && nj < W) {
                    flips ^= pressed[ni][nj];
                }
            }
            if (flips) {
                S[i][j] = (S[i][j] == '0' ? '1' : '0');
            }
        }
    }

    for (int i = 0; i < H; ++i) {
        cout << S[i] << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.