AOJ 2426 - 宝探し - ツバサの備忘録

解法

宝について、x座標の昇順であらかじめソートしておきます。
セグ木を用いて宝を管理していきます。
$[l,r)$ を表す頂点には、先ほどソートした宝の $[l,r)$ について、今度はy座標のみを取り出し、これを昇順に並べた数列を持たせます。
すると、あるクエリについて、与えられた長方形の左端が $l$ 、右端が $r$ 、下端が $d$ 、上端が $u$ のとき、
セグ木で $[l,r]$ を覆う頂点たちを取り出し、それぞれの頂点に存在する数列について、 $[d,u]$ の値の個数を二分探索で求めればよいです。