コンテンツにスキップ

ABC482 C - Band Count

サイト
AtCoder
コンテスト
ABC482
問題
C - Band Count
難易度
486

H×WH \times W のグリッドに NN 個の駒が置かれていて、ii 番目の駒はマス (Ri,Ci)(R_i, C_i) にあります。次の 22 種類のクエリ QQ 個に答える問題です(H,W≤109H, W \le 10^9、N,Q≤3×105N, Q \le 3 \times 10^5)。

  • 1 u d:uu 行目から dd 行目までにある駒の個数を出力する。
  • 2 l r:ll 列目から rr 列目までにある駒の個数を出力する。

行のクエリでは駒の列は関係なく、「u≤Ri≤du \le R_i \le d を満たす ii の個数」を答えればよいです。列のクエリも同様に「l≤Ci≤rl \le C_i \le r を満たす ii の個数」です。

H,WH, W が大きいので行ごとの個数の配列は作れませんが、RR と CC をそれぞれソートしておけば、二分探索で数えられます。ソートした RR で、dd 以下の個数から uu 未満の個数を引いたものが答えです。

計算量は O((N+Q)log⁡N)O((N + Q) \log N) です。

Python
import bisect
H, W, N, Q = map(int, input().split())
R = []
C = []
for _ in range(N):
r, c = map(int, input().split())
R.append(r)
C.append(c)
R.sort()
C.sort()
for _ in range(Q):
t, x, y = map(int, input().split())
l = R if t == 1 else C
print(bisect.bisect_right(l, y) - bisect.bisect_left(l, x))

bisect_right(l, y) は l の中の yy 以下の要素の個数、bisect_left(l, x) は xx 未満の要素の個数です。