CodeChef - Killing Monsters

• 問題
• AC

それぞれのモンスターについて、どの時点まで生きているかが高速に求まればよい。

クエリ$(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})$となる。