モノイドの列に対する作用 \(f_i\) が次の条件を満たすとする。

• \(f_i({A_1}^\frown A_2) = f_i({A_1})^\frown f_i(A_2)\)
• モノイドの列 \(A\) が性質 X を持つと、その任意の部分列 \(B \subseteq A\) について \(f_0(B)\) が \(T\) 時間で得られる。\(f_i\) (\(i \geq 1\)) は常に高速に計算できる。
• 長さ \(1\) の列は性質 X を持つ。
• 性質 X を満たさないセグメント木に含まれる部分列 B について、\(\phi(B)\) 回 \(f_0\) を作用させると性質 X を持つとする。\(\Phi := \sum_{B} \phi(B)\)とする。
  • 一回当たり、作用 \(f\) によって増加した \(\phi\) の増加量の \(\Phi\) への寄与の総和は高々 \(H\) である。
  • 一回当たり、作用 \(f_i\) (\(i\geq 1\)) によって \(\Phi\) は高々 \(H\) しか増加しない。

以上の条件が成り立つとき、\(f, g\) の作用がクエリ当たりならし \(O(HT)\) で計算できる。

yuki880
更新：\(L \leq i < R\) に対して \(a_i \leftarrow \gcd(a_i, x)\)
出力：\(\sum_{i=L}^{R-1} a_i\)

更新：\(L \leq i < R\) に対して \(a_i \leftarrow \min(a_i, x)\)
出力：\(\sum_{i=L}^{R-1} a_i\)

更新：\(L \leq i < R\) に対して \(a_i \leftarrow \min(a_i, x)\)
更新：\(L \leq i < R\) に対して \(a_i \leftarrow \max(a_i, x)\)
更新：\(L \leq i < R\) に対して \(a_i \leftarrow a_i+x\)
出力：\(\sum_{i=L}^{R-1} a_i\)

ABC256H
更新：\(L \leq i < R\) に対して \(a_i \leftarrow \lfloor a_i/x \rfloor\)
出力：\(\sum_{i=L}^{R-1} a_i\)

CSA70 And or Max
更新：\(L \leq i < R\) に対して \(a_i \leftarrow \text{bitwise_and}(a_i,x)\)
更新：\(L \leq i < R\) に対して \(a_i \leftarrow \text{bitwise_or}(a_i,x)\)
出力：\(\sum_{i=L}^{R-1} a_i\)

CF453E
\(\sum_{i=L}^{R-1} \min(a_i, x-b_i)\) を出力した後、\(L \leq i < R\) に対して \(b_i \leftarrow \min(b_i,x)\) とする。