区間mul 区間積 O(log N)
問題
長さNの整数列a_iが与えられます $Q$個のクエリを処理してください
- given l, r, x: $a_l \cdots a_r$を$x$倍
- given l, r: $a_l \times a_{l+1} \times \cdots \times a_r \bmod 998244353$を出力
$O(\log N)$ per queryで解けるがおそらく$O( \log^{2} N)$と識別不可能。
ちなみに元ネタはこれ(解法は違う): 区間代入/区間積 Θ(logN)/query - noshi91のメモ
$O(\log^{2} N)$ 解法
普通に遅延伝搬segtreeに乗せる。ノードには区間の総積と区間の長さを乗せる。ACL風に書くとS = pair<modint, int>
作用(mapping)の中でpow_modを呼ばないといけないため$O(\log^{2} N)$になる
$O(\log N)$ 解法
作用が可換なので遅延伝搬しない遅延伝搬segtree(何て呼ばれてるんでしょうこれ)が使える。 遅延伝搬しないverは次のようになる。もちろん素直に実装すると$O(\log^{2} N)$になるのだが、よく考えるとどちらも$O(\log N)$になる。
ノードごとに2つのmodint a, bを持つ。初期値はaが区間の総積でbが1
- mul: [l, r]をsegtreeの区間に分割する。分割された区間、およびその区間を子孫に持つすべての区間について
b *= x^([l, r]と自分の区間の共通部分の面積) - prod: [l, r]をsegtreeの区間に分割する。分割された区間それぞれについて、自分と先祖のbのprodを求め、cとする。そして
a * c^(区間の長さ)を求める。これをすべての区間について掛け合わせる
mulについては次のように高速化する。
- [l, r]を分割した区間: bにかかる係数は
x^(2^i)の形になっているので、まとめて$O(\log N)$で前計算できる - それ以外の区間: 子のbにかかる係数の積を自分のbに掛ければよい
prodについては次のように高速化する。
- cについてはdfsしながらまとめて計算できるので、結局ある数列$d_1, d_2, ..., d_k (k = \log N)$について $d_1 \times d_2^{2} \times d_3^{4} \cdots$ が求められれば良い。これは $d_1 \times square(d_2 \times square(d_3 \times ...)))$という形で計算すれば $O(\log N)$
