Toph - Subset of Master Shifu

• 問題
• AC

更新がなければwavelet matrixで解ける。更新がある場合、更新が起こる位置が高々6種類しかないことを利用できそう。列$B$を$A_1, ..., A_6$をそれぞれ含む/含まないという分類によって、$2^6 = 64$個の列に分解すると、更新は個々の部分列に対する定数加算として記録できる。質問クエリに対しては、各部分列の$[L, R]$に対応する区間について「$X$以下の要素は何個あるか？」という問いに答えられれば、その総和が$K$以上となるような最小の$X$が答えになるので二分探索できる。これはやはりwavelet matrixでできる。

計算量は、$A= \max(\max_i A_i, \max_i C_i), P=\max_i P_i$として、クエリあたり${O}((\log (AN))^2 2^P)$となる。（二分探索とwavelet matrixの処理が共に${O}(\log (AN))$。）かなり重いが$Q=10^4$で3秒なのでぎりぎり通る。

editorialを読んだ。ほぼ同じことをやっているようだが、wavelet matrixを64個用意する必要はなくて、1個用意すればほかはその列全体に定数を足したものになっている。確かに。オーダーは変わらないがだいぶ速くなった。