長方形区間カウント

点(x, y)がN個ある時に長方形区間$0\le x<T_x,0\le y<T_y$の点の数を数える問題

• $0\le x,y<M$とする

特に各点$(x_i,y_i)$について ${\sum }_j[x_j<x_i][y_j<y_i]$を計算する場合

• 素朴にループで書くとO(N^2)なのでNが大きい時に工夫が必要

• 二次元の片方を時間軸にする

  • xでソートしてそれを時間軸にする

• フェニック木

  • yを定義域にする

• x < x0がすべて追加されている状態でy < y0を満たすものの数が分かれば良い

  • 定義域をy、値域を出現回数とすればsumで求まる

• 同じxの点がある場合、事前にxでグループ化して、sumをし終わってからaddする必要がある python

# grouping
from collections import defaultdict
P2 = defaultdict(list)
for i in range(M):
    x, y = PS[i]
    P2[y - 1].append(x - 1)

bit_init(H + 1)
for y in range(0, y0):
    ret += bit_sum(x0)
    for x in P2[y]:
        bit_add(x, 1)

• ABC186F
  • 範囲内の個数ではなく、ブロックされている列の個数を知りたいのでbit_addではなくbit_setした
• 二次元累積和
  • https://algo-logic.info/submatrix-sum-queries/ 長方形クエリ