累積和(2次元)③

問題

ある地域を H×W のマス目で表します。

最初は、どのマスにも雪が積もっていませんでしたが、これから N 日間に渡って雪が降り続けます。

上から i 行目、左から j 列目のマスを (i,j) とするとき、t 日目にはマス(At,Bt)を左上とし、マス(Ct,Dt)を右下とする長方形領域の積雪が1cmだけ増加することが予想されています。

最終的な各マスの積雪を出力してください。

[制約]
🔹1H,W1500
🔹1N100000
🔹1AiCiH
🔹1BiDiW

解き方・ソースコード

この問題も累積和を使って、少ない計算量で解くことができます。

具体的には前の要素との差分を計算し、その累積和をとることで解いていきます。

🔹マス (a,b) およびマス (c+1,d+1)+1 する。【ソースコード 14~15行目】
🔹マス (a,d+1) およびマス (c+1,b)1 する。【ソースコード 16~17行目】
🔹2次元累積和をとる。(左から右への横の累積和をとったあとに、上から下への縦の累積和をとる)【ソースコード 20~25行目】


前計算に O(N) かかり、2次元累積和をとる処理に O(HW) かかるので、プログラム全体の計算量は O(N+HW) となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#-------- 入力例1 ---------
H = 5
W = 5
N = 3
A = [1, 3, 2]
B = [1, 3, 2]
C = [3, 5, 4]
D = [3, 5, 4]
#---------------------------
# 各日について加算
X = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
Z = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
for t in range(N):
X[A[t]][B[t]] += 1
X[C[t] + 1][D[t] + 1] += 1
X[A[t]][D[t] + 1] -= 1
X[C[t] + 1][B[t]] -= 1

# 二次元累積和を算出
for i in range(1, H + 1):
for j in range(1, W + 1):
Z[i][j] = Z[i][j - 1] + X[i][j]
for j in range(1, W+1):
for i in range(1, H + 1):
Z[i][j] = Z[i - 1][j] + Z[i][j]

# 出力
for i in range(1, H + 1):
for j in range(1, W + 1):
if j >= 2:
print(' ', end='')
print(Z[i][j], end='')
print()

[実行結果(入力例1)]

1 1 1 0 0

1 2 2 1 0

1 2 3 2 1

0 1 2 2 1

0 0 1 1 1

各マスの積雪を表示することができました。