Official
D - 照明の切り替え / Switching the Lights Editorial
by
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\) を加算することで答えを求めることができます。
以下の実装例では各ボタンが何回押されたかを持たず、その偶奇の情報のみを持っています。
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:
