累積和（２次元）④

問題

２次元平面上に $N$ 個の点があり、$i$ 個めの点の座標は$(X_i,Y_i)$です。

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

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq 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
import random
#-------- 入力例１ ---------
N = 100000
X = [random.randint(1, 1500) for _ in range(N)] 
Y = [random.randint(1, 1500) for _ in range(N)] 
Q = 100000
A = [random.randint(1, 1500 - 1) for _ in range(Q)]
B = [random.randint(1, 1500 - 1) for _ in range(Q)]
C = [random.randint(A[i] + 1, 1500) for i in range(Q)]
D = [random.randint(B[i] + 1, 1500) for i in range(Q)]
#---------------------------
# 各座標にある点の数をカウント
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(f'質問{i + 1}番目の解：', T[C[i]][D[i]] + T[A[i] - 1][B[i] - 1] - T[A[i] - 1][D[i]] - T[C[i]][B[i] - 1], '個')

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

質問1番目の解： 841 個

質問2番目の解： 3303 個

質問3番目の解： 1359 個

質問4番目の解： 12495 個

　　　　：

　　（中略）

　　　　：

質問99997番目の解： 86 個

質問99998番目の解： 2975 個

質問99999番目の解： 9480 個

質問100000番目の解： 24764 個

各座標に何個の点があるかを算出できました。