累積和（２次元）③

問題

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

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

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

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

[制約]
🔹$ 1 \leqq H,W \leqq 1500 $
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq C_i \leqq H $
🔹$ 1 \leqq B_i \leqq D_i \leqq 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

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