Official

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


\(r1,c1,r2,c2\) の情報から各ボタンが何回押されたかを計算することを考えます。

毎回長方形領域に加算すると計算量が多く TLE となってしまうので、2 次元 imos 法 と呼ばれる手法を考えます。

2 次元 imos 法を用いることで、\((i,j)\) のボタンが押された回数 \(A_{i,j}\) は以下のように計算することができます:

  • 全ての \(i,j\) に対し \(A_{i,j}=0\) とする。
  • \(k=1,2,\ldots,Q\) に対し、以下を行う:
    • \(A_{r1_k,c1_k}\) を \(1\) 増やす。
    • \(A_{r2_k+1,c1_k}\) を \(1\) 減らす。
    • \(A_{r1_k,c2_k+1}\) を \(1\) 減らす。
    • \(A_{r2_k+1,c2_k+1}\) を \(1\) 増やす。
  • \(i=1,2,\ldots,N\) と \(j=1,2,\ldots,M-1\) に対し、\(A_{i,j+1}\) に \(A_{i,j}\) を加算する。
  • \(i=1,2,\ldots,N-1\) と \(j=1,2,\ldots,M\) に対し、\(A_{i+1,j}\) に \(A_{i,j}\) を加算する。

以上を実装し、各マスが何回押されたかを元に適切に \(B\) を加算することで答えを求めることができます。

以下の実装例では各ボタンが何回押されたかを持たず、その偶奇の情報のみを持っています。

実装例(Python3)

import sys

input = sys.stdin.readline
n, m, q = map(int, input().split())
b = [list(map(int, input().split())) for i in range(n)]
a = [[0] * (m + 1) for i in range(n + 1)]
for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    r1 -= 1
    c1 -= 1
    a[r1][c1] ^= 1
    a[r1][c2] ^= 1
    a[r2][c1] ^= 1
    a[r2][c2] ^= 1
for i in range(n):
    for j in range(m):
        a[i + 1][j] ^= a[i][j]
for i in range(n):
    for j in range(m):
        a[i][j + 1] ^= a[i][j]
ans = 0
for i in range(n):
    for j in range(m):
        ans += (1 + a[i][j]) * b[i][j]
print(ans)

posted:
last update: