長方形区間カウント

点(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する必要がある

code:python

# grouping

from collections import defaultdict

P2 = defaultdict(list)

for i in range(M):

x, y = PSi

P2y - 1.append(x - 1)

bit_init(H + 1)

for y in range(0, y0):

ret += bit_sum(x0)

for x in P2y:

bit_add(x, 1)

範囲内の個数ではなく、ブロックされている列の個数を知りたいのでbit_addではなくbit_setした