区間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)$