Atcoder 備忘録_二次元累積和_問題B08

概要

• 競技プログラミングを始めてみた。
  せっかくなので１テーマごとに解法と学びをアウトプットしてみる。

取り組む内容

• 鉄則本[https://atcoder.jp/contests/tessoku-book] に沿って実施する。
• 
• 言語は Python
• 今回テーマは「二次元累積和」

問題文

二次元平面上にN個の点があります．i個目の点の座標は(Xi,Yi) です．「x座標がa以上c以下でありy座標がb以上d以下であるような点は何個あるか？」という形式の質問がQ個与えられるので，それぞれの質問に答えるプログラムを実装してください
なお，入力される値はすべて整数です．

制約

• 1≤N,Q≤100000
• 1≤Xi,Yi≤1500
• 1≤ai≤ci≤1500
• 1≤bi≤di≤1500
• 入力はすべて整数

出力

Q行にわたって出力してください。i行目には，i個目の質問の答えを出力してください

解法

N = int(input())

Xi = [0] * N
Yi = [0] * N

for n in range(N):
  Xi[n], Yi[n] = map(int, input().split())

Q = int(input())
Ai = [0] * Q
Bi = [0] * Q
Ci = [0] * Q
Di = [0] * Q

for q in range(Q):
  Ai[q], Bi[q], Ci[q], Di[q] = map(int, input().split())
  
matrix = [[0] * 1501 for i in range(1501)]

for n in range(N):
  matrix[Xi[n]][Yi[n]] += 1
  
for i in range(1501):
  for j in range(1, 1501):
    matrix[i][j] += matrix[i][j-1]
    
for j in range(1501):
  for i in range(1, 1501):
    matrix[i][j] += matrix[i-1][j]

for q in range(Q):
  print(matrix[Ci[q]][Di[q]] + matrix[Ai[q]-1][Bi[q]-1] - matrix[Ai[q]-1][Di[q]] - matrix[Ci[q]][Bi[q]-1])
  

結果

• AC
• Runtime： 1069 ms
• メモリ：116428 KB

振り返り

思想

• (ai, bi), (ci, di)区間での点の個数は二次元累積和Sに対して S[ci][di] + S[ai-1][bi-1] - S[ai-1][di] - S[ci][bi-1]で求められる

感想

• マトリックスになると頭のなかでイメージするの中々難しくなる