それぞれのモンスターについて、どの時点まで生きているかが高速に求まればよい。
クエリ$(x, y)$が与えられたとき、$x$に（bit集合の意味で）包含されるようなすべての番号のモンスターから$y$を引くことになる。
- $f[t] :=x =t$であるようなクエリの総ダメージ。
- $F[t] :=x \supseteq t$であるようなクエリの総ダメージ。
とするとき、関心があるのは$F$で、$F$は$f$からゼータ変換で得られる。各クエリを処理した時点での$F$が配列として$q$個分すべて求まっているとすると、それらをクエリ番号に関して二分探索することで各モンスターがどの時点まで生きているかがわかる……が、$F$を毎回作ると間に合わない。
そこで、クエリを$B$個ずつに分割して、$q/B$個のクエリ番号に対してのみ$F$を作ることにする。 モンスター$k$がどの分割まで生きているかを線形探索（あるいは二分探索）で調べて、そこからはモンスターが死ぬまでクエリを一つずつ見ていく。
前半の計算量は${O}((q/B) n\log n)$で、後半は${O}((q/B + B)n)$。$B = \sqrt {q \log n}$とすると全体の計算量は${O}(n \sqrt {q \log n})$となる。
