D - 照明の切り替え / Switching the Lights 解説 by admin
Claude 4.6 Opus (Thinking)Overview
Given an \(N \times M\) grid of lights, we perform \(Q\) rectangular region switch operations and calculate the total brightness based on whether each light was pressed an odd or even number of times.
Analysis
Key Insight: Only Parity Matters
The final brightness of each light depends solely on the parity of the number of times the switch was pressed. If pressed an odd number of times, the brightness is \(2 \times B_{i,j}\); if pressed an even number of times, it is \(B_{i,j}\). We don’t need to count the exact number of presses — we only need to know whether it’s odd or even.
Problem with the Naive Approach
If we update every light in the specified rectangular region for each of the \(Q\) operations, a single operation may process up to \(N \times M = 1500 \times 1500 = 2.25 \times 10^6\) cells. Over all \(Q\) operations, this requires up to \(Q \times N \times M \approx 4.5 \times 10^{11}\) operations, which is far too slow.
Solution: 2D Imos Method (XOR Version)
In the standard 2D imos method (difference array as the inverse of prefix sums), adding a value to a rectangular region can be compressed into operations on 4 corner points. Since only the parity of the count matters here, we use XOR instead of addition. Because XOR corresponds to toggling parity (\(0 \oplus 1 = 1\), \(1 \oplus 1 = 0\)), we can take the prefix XOR instead of the prefix sum.
Algorithm
- Building the Difference Array: Initialize a difference array
diffof size \((N+2) \times (M+2)\) with \(0\). For each operation \((r1, c1, r2, c2)\), update the following 4 points using XOR:diff[r1][c1] ^= 1diff[r1][c2+1] ^= 1diff[r2+1][c1] ^= 1diff[r2+1][c2+1] ^= 1
This is simply replacing +1 with XOR 1 compared to the standard 2D imos method.
- Restoring with Prefix XOR: First, take the prefix XOR along the row direction (left to right), then along the column direction (top to bottom). After this,
diff[i][j]stores the parity (\(0\) or \(1\)) of the number of times the switch at cell \((i, j)\) was pressed.
Concrete Example: For a 3×3 grid with a single operation \((1,1,2,2)\), the 4 corners of the difference array are set to \(1\), and after taking the prefix XOR, only the range \((1,1)\) to \((2,2)\) becomes \(1\).
- Computing the Total: For each cell \((i, j)\), if
diff[i][j]is \(1\) (odd number of presses), add \(2 \times B_{i,j}\) to the total; if \(0\) (even number of presses), add \(B_{i,j}\) to the total.
Complexity
- Time Complexity: \(O(N \times M + Q)\)
- Updating the difference array is \(O(1)\) per operation, totaling \(O(Q)\)
- Restoring the prefix XOR and computing the total is \(O(N \times M)\)
- Space Complexity: \(O(N \times M)\)
- For storing the difference array and the grid
Implementation Notes
Imos Method with XOR: When only parity is needed, XOR and prefix XOR can be used instead of addition and prefix sums. XOR can be written concisely as
a ^= b.Be Careful with Array Size: Since the difference array accesses
r2+1andc2+1, the array must be allocated with size \((N+2) \times (M+2)\).Fast Input: Since \(N, M\) can be up to 1500 and \(Q\) up to \(2 \times 10^5\), which are large values, in Python we speed up input by reading all at once with
sys.stdin.buffer.read().Source Code
import sys
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
Q = int(input_data[idx]); idx += 1
B = []
for i in range(N):
row = [int(input_data[idx + j]) for j in range(M)]
idx += M
B.append(row)
# 2D difference array for counting switch presses (parity)
# Using imos method on (N+2) x (M+2) grid
diff = [[0] * (M + 2) for _ in range(N + 2)]
for _ in range(Q):
r1 = int(input_data[idx]); idx += 1
c1 = int(input_data[idx]); idx += 1
r2 = int(input_data[idx]); idx += 1
c2 = int(input_data[idx]); idx += 1
diff[r1][c1] ^= 1
diff[r1][c2 + 1] ^= 1
diff[r2 + 1][c1] ^= 1
diff[r2 + 1][c2 + 1] ^= 1
# Compute prefix XOR row-wise then column-wise
for i in range(1, N + 1):
for j in range(1, M + 1):
diff[i][j] ^= diff[i][j - 1]
for j in range(1, M + 1):
for i in range(1, N + 1):
diff[i][j] ^= diff[i - 1][j]
total = 0
for i in range(1, N + 1):
for j in range(1, M + 1):
b = B[i - 1][j - 1]
if diff[i][j] & 1:
total += 2 * b
else:
total += b
print(total)
main()
This editorial was generated by claude4.6opus-thinking.