Official

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

GPT 5.2 High

概要

長方形領域の「反転操作(押した回数の偶奇)」を \(Q\) 回行ったあと、各マスが奇数回押されたかどうかだけを求め、最終的な明るさの総和を計算する問題です。

考察

各照明は押すたびに通常↔強調と切り替わるので、最終状態に必要なのは「押された回数の偶奇」だけです(偶数回なら元のまま、奇数回なら \(2B\))。

素朴に各操作ごとに長方形内を全部反転すると、1 回の操作が最大 \(N \times M\) マスを含み得るため、最悪で \(O(QNM)\) となり(\(1500^2 \times 2\times10^5\) など)到底間に合いません。

そこで、「長方形への一括加算」を高速に処理できる 2次元いもす法(2次元差分配列) を使います。
各操作を差分配列に \(O(1)\) で記録し、最後に累積和を取ることで「各マスが何回押されたか」をまとめて復元できます。必要なのは偶奇なので、復元した値を \(2\) で割った余り(ビットで言えば & 1)だけ見れば十分です。

また、最終的な総和は - 全マスの基礎値の合計 \(S=\sum B_{i,j}\) - 奇数回押されたマスだけ、追加で \(+B_{i,j}\)(\(B \to 2B\) なので差分は \(+B\))

より、答えは
\(S + \sum_{\text{odd}} B_{i,j}\)
と計算できます。

アルゴリズム

  1. 入力された明るさ \(B_{i,j}\) を読み込み、基礎合計 \(S=\sum B_{i,j}\) を求めておく。
  2. \((N+2)\times(M+2)\) の差分配列 diff を用意する(端の処理を楽にするために外枠を持たせる)。
  3. 各クエリ長方形 \((r1,c1)-(r2,c2)\) について、2次元いもす法の更新を行う:
    • diff[r1][c1] += 1
    • diff[r2+1][c1] -= 1
    • diff[r1][c2+1] -= 1
    • diff[r2+1][c2+1] += 1 これで「この長方形を +1 回押した」という情報を \(O(1)\) で記録できる。
  4. 最後に diff の2次元累積和を取り、各マスの押された回数 cnt[i][j] を復元する。復元式は $\( cnt[i][j] = diff[i][j] + cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] \)$ (実装では diff をそのまま累積和で上書きしている)。
  5. cnt[i][j] が奇数ならそのマスは強調モードなので、追加分として extra += B[i][j] を足す。
  6. 答えは S + extra。

(例)あるマスが 3 回押されていれば奇数なので \(B \to 2B\)、合計には追加で \(+B\) だけ寄与します。2 回なら偶数なので変化なしです。

計算量

  • 時間計算量: \(O(NM + Q)\)
    (差分更新が \(Q\) 回で \(O(Q)\)、累積和+判定が全マスで \(O(NM)\))
  • 空間計算量: \(O(NM)\)
    (差分配列と明るさ配列を保持)

実装のポイント

  • 2次元いもす法の4点更新(左上に +、右側と下側に -、右下に +)を間違えないこと。

  • 累積和の計算で cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] の「引き算」を忘れると二重に数えてしまいます。

  • 偶奇だけ見ればよいので、復元後に cnt & 1 で判定すると高速です。

  • Python では大きい2次元リストは遅く/重くなりがちなので、コードでは array と1次元化(index = i*W + j)で高速化しています。

    ソースコード

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()

この解説は gpt-5.2-high によって生成されました。

posted:
last update: