累積和（２次元）②

問題

２次元平面上に $ N $ 個の点があります。

$ i $ 個めの座標は $ (X_i,Y_i) $ です。

『$x$ 座標が $ a $ 以上 $ c $ 以下であり、$ y $ 座標が $ b $ 以上 $ d $ 以下であるような点は何個あるか』という質問が $ Q $ 個与えられるので、それぞれの質問に答えて下さい。

[制約]
🔹$ N \leqq 100000 $
🔹$ Q \leqq 100000 $
🔹$ 1 \leqq X_i,Y_i \leqq 1500 $

解き方・ソースコード

この問題ではまず、各座標に何個の点があるのかを、２次元配列を使って算出します。

次に横方向の累積和をとった後、縦方法の累積和をとり、最後に計算した２次元の累積和を使って、質問される座標範囲の合計値を求めます。

（合計値を算出する式は、前回記事をご参照ください。）

[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
import random
#--------- 入力例1 ---------
N = 100      # 座標の数
X = [random.randint(1, 1500) for _ in range(N)]     # 各X座標
Y = [random.randint(1, 1500) for _ in range(N)]     # 各Y座標

Q = 10      # 質問の数
A = [random.randint(1, 750) for _ in range(N)]     # 座標範囲の開始X座標
B = [random.randint(1, 750) for _ in range(N)]     # 座標範囲の開始Y座標
C = [random.randint(750, 1500) for _ in range(N)]  # 座標範囲の終了X座標
D = [random.randint(750, 1500) for _ in range(N)]  # 座標範囲の終了Y座標
#---------------------------
# 各座標にある点の数を数える
S = [[0] * 1501 for i in range(1501) ]
for i in range(N):
    S[X[i]][Y[i]] += 1

# 累積和をとる
T = [[0] * 1501 for i in range(1501) ]
for i in range(1, 1501):
    for j in range(1, 1501):
        T[i][j] = T[i][j - 1] + S[i][j]
for j in range(1, 1501):
    for i in range(1, 1501):
        T[i][j] = T[i - 1][j] + T[i][j]

# 答えを算出する
for i in range(Q):
    print('座標({}, {})から座標({}, {})の範囲にある点の数は{}個'.format(
           A[i], B[i], C[i], D[i],
           T[C[i]][D[i]] + T[A[i] - 1][B[i] - 1] - T[A[i] - 1][D[i]] - T[C[i]][B[i] - 1]))

[実行結果（入力例１）]

座標(635, 592)から座標(1075, 1360)の範囲にある点の数は16個

座標(705, 478)から座標(905, 1136)の範囲にある点の数は7個

座標(7, 491)から座標(952, 1227)の範囲にある点の数は32個

座標(593, 550)から座標(1028, 1242)の範囲にある点の数は11個

座標(597, 673)から座標(1340, 1455)の範囲にある点の数は22個

座標(584, 473)から座標(765, 1237)の範囲にある点の数は9個

座標(366, 521)から座標(1207, 756)の範囲にある点の数は11個

座標(642, 504)から座標(1254, 1057)の範囲にある点の数は12個

座標(543, 538)から座標(1180, 801)の範囲にある点の数は7個

座標(633, 394)から座標(1059, 1114)の範囲にある点の数は14個

各座標の範囲にある点の数を求めることができました。

（各座標はランダムに生成しているため、実行するたびに結果は変わります。）