公式

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

Qwen3-Coder-480B

Overview

Given an \(N \times M\) grid where each cell has a light, multiple switch operations are performed on rectangular regions, and we need to find the total brightness at the end.

Analysis

If a light’s switch is pressed an odd number of times, it enters “enhanced mode” (brightness doubled), and if pressed an even number of times, it stays in “normal mode” (brightness unchanged). Therefore, only the parity of the number of times each light’s switch is pressed matters.

A naive approach would be to directly update the count for every cell within the specified rectangular region for each operation. However, when the number of operations \(Q\) is up to \(2 \times 10^5\) and the grid size is also large, this approach requires up to \(Q \times N \times M\) computations in total, which will not meet the time limit (TLE).

Instead, we use a technique called “2D imos method (two-dimensional extension of the imos method).” This is a difference-based update technique for efficiently performing range additions. It transforms the increment over a rectangular region into setting values at four points, and then taking prefix sums at the end to obtain the switch count for each cell. This allows each operation to be processed in constant time, making the overall solution fast.

Algorithm

  1. Reading Input
    Read the initial brightness \(B_{i,j}\) of the grid and the information for \(Q\) operations.

  2. Preparing the Difference Array
    Prepare a 2D array diff of size \((N+1) \times (M+1)\). This is a difference table for recording the increment in switch counts from each operation.

  3. Applying Operations (2D imos method)
    For the rectangular region from \((r1, c1)\) to \((r2, c2)\) specified by each operation, set the differences as follows:

    • diff[r1][c1] += 1
    • diff[r1][c2+1] -= 1
    • diff[r2+1][c1] -= 1
    • diff[r2+1][c2+1] += 1
  4. Computing Prefix Sums and Parity Check
    Compute the 2D prefix sum on the diff array to obtain the number of switch operations for each cell \((i, j)\). If the remainder when dividing that value by 2 (mod 2) is 1, the switch was pressed an odd number of times; if 0, an even number of times.

  5. Computing the Final Brightness
    For each cell, based on the parity, add either \(B_{i,j}\) or \(2 \times B_{i,j}\) to the total sum.

Complexity

  • Time complexity: \(O(N \times M + Q)\)
  • Space complexity: \(O(N \times M)\)

Implementation Notes

  • Note that coordinates are converted to 0-indexed (input is 1-indexed)

  • The difference array is sized \((N+1) \times (M+1)\) to simplify boundary handling

  • Conditional branches are included during prefix sum computation to prevent out-of-bounds access

    Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    B = [[0]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            B[i][j] = int(data[idx])
            idx += 1
    
    # 差分更新用の2D累積和配列
    diff = [[0]*(M+1) for _ in range(N+1)]
    
    for _ in range(Q):
        r1 = int(data[idx]) - 1; idx += 1
        c1 = int(data[idx]) - 1; idx += 1
        r2 = int(data[idx]) - 1; idx += 1
        c2 = int(data[idx]) - 1; idx += 1
        
        # 2D差分更新
        diff[r1][c1] += 1
        diff[r1][c2+1] -= 1
        diff[r2+1][c1] -= 1
        diff[r2+1][c2+1] += 1
    
    # 2D累積和を計算して各セルのスイッチ回数の偶奇を求める
    count = [[0]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            v = diff[i][j]
            if i > 0:
                v += diff[i-1][j]
            if j > 0:
                v += diff[i][j-1]
            if i > 0 and j > 0:
                v -= diff[i-1][j-1]
            diff[i][j] = v
            count[i][j] = v % 2
    
    # 各照明の最終的な明るさを計算
    total = 0
    for i in range(N):
        for j in range(M):
            if count[i][j] == 1:
                total += 2 * B[i][j]
            else:
                total += B[i][j]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.