累積和（２次元）③

問題

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

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

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

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

[制約]
🔹1≦H,W≦1500
🔹1≦N≦100000
🔹1≦Ai≦Ci≦H
🔹1≦Bi≦Di≦W

解き方・ソースコード

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

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

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

前計算に O(N) かかり、２次元累積和をとる処理に 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
#-------- 入力例１ ---------
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 0 0

1 2 2 1 0

1 2 3 2 1

0 1 2 2 1

0 0 1 1 1

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