D - 照明の切り替え / Switching the Lights 解説 by admin
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}\)
と計算できます。
アルゴリズム
- 入力された明るさ \(B_{i,j}\) を読み込み、基礎合計 \(S=\sum B_{i,j}\) を求めておく。
- \((N+2)\times(M+2)\) の差分配列
diffを用意する(端の処理を楽にするために外枠を持たせる)。 - 各クエリ長方形 \((r1,c1)-(r2,c2)\) について、2次元いもす法の更新を行う:
diff[r1][c1] += 1diff[r2+1][c1] -= 1diff[r1][c2+1] -= 1diff[r2+1][c2+1] += 1これで「この長方形を +1 回押した」という情報を \(O(1)\) で記録できる。
- 最後に
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をそのまま累積和で上書きしている)。 cnt[i][j]が奇数ならそのマスは強調モードなので、追加分としてextra += B[i][j]を足す。- 答えは
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 によって生成されました。