Official

D - 照明の切り替え / Switching the Lights Editorial by admin

GPT 5.2 High

Overview

This is a problem where, after performing \(Q\) rectangular region “toggle operations (parity of the number of presses),” we need to determine whether each cell was pressed an odd number of times and compute the total sum of brightness values.

Analysis

Since each light toggles between normal and enhanced mode with each press, all that matters for the final state is the parity of the number of presses (even means unchanged, odd means \(2B\)).

Naively toggling every cell within the rectangle for each operation could affect up to \(N \times M\) cells per operation, resulting in a worst case of \(O(QNM)\) (e.g., \(1500^2 \times 2\times10^5\)), which is far too slow.

Instead, we use 2D imos method (2D difference array), which efficiently handles batch additions over rectangular regions.
Each operation is recorded in the difference array in \(O(1)\), and at the end, we take the prefix sum to recover “how many times each cell was pressed.” Since we only need the parity, it suffices to check the remainder when dividing by \(2\) (in terms of bits, just & 1).

Furthermore, the final sum can be computed as: - The sum of base values of all cells: \(S=\sum B_{i,j}\) - For cells pressed an odd number of times, an additional \(+B_{i,j}\) (since \(B \to 2B\), the difference is \(+B\))

Therefore, the answer is:
\(S + \sum_{\text{odd}} B_{i,j}\)

Algorithm

  1. Read the brightness values \(B_{i,j}\) and compute the base total \(S=\sum B_{i,j}\).
  2. Prepare a difference array diff of size \((N+2)\times(M+2)\) (with an outer border to simplify boundary handling).
  3. For each query rectangle \((r1,c1)-(r2,c2)\), perform the 2D imos method update:
    • diff[r1][c1] += 1
    • diff[r2+1][c1] -= 1
    • diff[r1][c2+1] -= 1
    • diff[r2+1][c2+1] += 1 This records the information “this rectangle was pressed +1 time” in \(O(1)\).
  4. Finally, take the 2D prefix sum of diff to recover the press count cnt[i][j] for each cell. The recovery formula is: $\( cnt[i][j] = diff[i][j] + cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] \)$ (In the implementation, diff is overwritten in-place with the prefix sum.)
  5. If cnt[i][j] is odd, that cell is in enhanced mode, so add extra += B[i][j].
  6. The answer is S + extra.

(Example) If a cell was pressed 3 times, that’s odd, so \(B \to 2B\), contributing an additional \(+B\) to the total. If pressed 2 times, that’s even, so there is no change.

Complexity

  • Time complexity: \(O(NM + Q)\)
    (Difference updates are \(O(Q)\) for \(Q\) operations, and the prefix sum + parity check is \(O(NM)\) over all cells)
  • Space complexity: \(O(NM)\)
    (For storing the difference array and the brightness array)

Implementation Notes

  • Be careful not to make mistakes with the 4-point update of the 2D imos method (+ at top-left, - at the right side and bottom side, + at bottom-right).

  • Forgetting the “subtraction” cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] in the prefix sum calculation will result in double counting.

  • Since we only need the parity, checking cnt & 1 after recovery is efficient.

  • In Python, large 2D lists tend to be slow/heavy, so the code uses array with 1D linearization (index = i*W + j) for optimization.

    Source Code

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())

    B = array('I', [0]) * (N * M)
    base_sum = 0
    pos = 0
    for _ in range(N):
        for v in map(int, input().split()):
            B[pos] = v
            base_sum += v
            pos += 1

    W = M + 2
    diff = array('i', [0]) * ((N + 2) * W)

    for _ in range(Q):
        r1, c1, r2, c2 = map(int, input().split())
        diff[r1 * W + c1] += 1
        diff[(r2 + 1) * W + c1] -= 1
        diff[r1 * W + (c2 + 1)] -= 1
        diff[(r2 + 1) * W + (c2 + 1)] += 1

    extra = 0
    b_idx = 0
    diff_local = diff
    B_local = B
    W_local = W
    M_local = M

    for i in range(1, N + 1):
        idx = i * W_local + 1
        for _ in range(M_local):
            diff_local[idx] += diff_local[idx - 1] + diff_local[idx - W_local] - diff_local[idx - W_local - 1]
            if diff_local[idx] & 1:
                extra += B_local[b_idx]
            idx += 1
            b_idx += 1

    print(base_sum + extra)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.