D - 照明の切り替え / Switching the Lights 解説 by admin 印刷ページ
DeepSeek V3Overview
This problem asks us to repeatedly perform operations that toggle the switches of lights within specified rectangular regions, then find the total brightness of all lights.
Analysis
In a naive approach, if we try to record the switch operation for every light within the rectangular region for each operation, a single operation would update up to \(N \times M\) elements, requiring a total computational complexity of \(O(Q \times N \times M)\). Given the constraints \(N, M \leq 1500\) and \(Q \leq 200000\), this would require \(1500 \times 1500 \times 200000 = 4.5 \times 10^{11}\) operations, which is infeasible to compute within a realistic time limit.
Therefore, to efficiently determine the number of times each light’s switch has been pressed, we use a two-dimensional prefix sum (or two-dimensional imos method). By marking only the four corners of the rectangular region for each operation and then computing the prefix sum at the end, we can efficiently calculate the number of times each light’s switch was pressed.
Algorithm
- Create a two-dimensional difference array: Create an array
diffof size \((N+2) \times (M+2)\) (the +2 is to prevent out-of-bounds access). - Record operations: For each operation \((r1, c1, r2, c2)\), update the following 4 points:
diff[r1][c1] += 1diff[r1][c2+1] -= 1diff[r2+1][c1] -= 1diff[r2+1][c2+1] += 1
- Compute prefix sums: Calculate the two-dimensional prefix sum to obtain
total_switches[i][j], the number of times each light \((i, j)\) had its switch pressed. - Calculate brightness: For each light, if the number of switch presses is odd, the brightness is \(2 \times B_{i,j}\); if even, the brightness is \(B_{i,j}\). Sum up all these values.
Complexity
- Time complexity: \(O(N \times M + Q)\)
- Computing the prefix sum takes \(O(N \times M)\), and recording the operations takes \(O(Q)\).
- Space complexity: \(O(N \times M)\)
- This is for storing the difference array and the prefix sum array.
Implementation Notes
Be careful with array indices: the input grid is 0-indexed, but the difference array is handled as 1-indexed.
To prevent out-of-bounds access, the array size is set to \((N+2) \times (M+2)\).
When computing the prefix sum, process from the top-left corner using the formula:
total_switches[i][j] = diff[i][j] + total_switches[i-1][j] + total_switches[i][j-1] - total_switches[i-1][j-1].Source Code
def main():
import sys
data = sys.stdin.read().split()
idx = 0
N = int(data[idx]); M = int(data[idx+1]); Q = int(data[idx+2]); idx += 3
grid = []
for i in range(N):
row = list(map(int, data[idx:idx+M]))
idx += M
grid.append(row)
diff = [[0] * (M+2) for _ in range(N+2)]
for i in range(Q):
r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
diff[r1][c1] += 1
diff[r1][c2+1] -= 1
diff[r2+1][c1] -= 1
diff[r2+1][c2+1] += 1
total_switches = [[0] * (M+2) for _ in range(N+2)]
for i in range(1, N+1):
for j in range(1, M+1):
total_switches[i][j] = diff[i][j] + total_switches[i-1][j] + total_switches[i][j-1] - total_switches[i-1][j-1]
ans = 0
for i in range(1, N+1):
for j in range(1, M+1):
switches = total_switches[i][j]
if switches % 2 == 0:
ans += grid[i-1][j-1]
else:
ans += 2 * grid[i-1][j-1]
print(ans)
if __name__ == "__main__":
main()
This editorial was generated by deepseekv3.
投稿日時:
最終更新: