解法
宝について、x座標の昇順であらかじめソートしておきます。
セグ木を用いて宝を管理していきます。
を表す頂点には、先ほどソートした宝の
について、今度はy座標のみを取り出し、これを昇順に並べた数列を持たせます。
すると、あるクエリについて、与えられた長方形の左端が、右端が
、下端が
、上端が
のとき、
セグ木でを覆う頂点たちを取り出し、それぞれの頂点に存在する数列について、
の値の個数を二分探索で求めればよいです。
感想
問題を読み終えた時点でこれはセグ木だなーって思ってしまったのですが、想定解を見たらセグ木を使っていなかったので賢いなーと思いました…
