D - 照明の切り替え / Switching the Lights Editorial by admin
GPT 5.2 HighOverview
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
- Read the brightness values \(B_{i,j}\) and compute the base total \(S=\sum B_{i,j}\).
- Prepare a difference array
diffof size \((N+2)\times(M+2)\) (with an outer border to simplify boundary handling). - For each query rectangle \((r1,c1)-(r2,c2)\), perform the 2D imos method update:
diff[r1][c1] += 1diff[r2+1][c1] -= 1diff[r1][c2+1] -= 1diff[r2+1][c2+1] += 1This records the information “this rectangle was pressed +1 time” in \(O(1)\).
- Finally, take the 2D prefix sum of
diffto recover the press countcnt[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,diffis overwritten in-place with the prefix sum.) - If
cnt[i][j]is odd, that cell is in enhanced mode, so addextra += B[i][j]. - 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 & 1after recovery is efficient.In Python, large 2D lists tend to be slow/heavy, so the code uses
arraywith 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.