No.619

Segment Tree で管理する.

Segment Tree の要素は積演算の和として表したときの初項, 末項と残りをまとめたものとする.

すなわち, $1 \times 2 + 3 \times 4 \times 5 + 6 + 7 \times 8$ の場合は, $(1 \times 2, 3 \times 4 \times 5 + 6, 7 \times 8) = (2, 66, 72)$ である.

これで2つの区間をまとめるとき, 各区間の要素を $(a_1, b_1, c_1)$, $(a_2, b_2, c_2)$ とすると,

$$\begin{align} (a_1, b_1, c_1) + (a_2, b_2, c_2) &= (a_1, b_1 + c_1 + a_2 + b_2, c_2) \\ (a_1, b_1, c_1) \times (a_2, b_2, c_2) &= (a_1, b_1 + c_1 \times a_2 + b_2, c_2) \end{align}$$

という感じでまとめられる. ただし, 積演算の和として表したときに1項目しかない場合は特別扱いする. 1項目しかない場合は $(d_i)$ と表すとすると,

$$\begin{align} (d_1) + (d_2) &= (d_1, 0, d_2) \\ (d_1) \times (d_2) &= (d_1 \times d_2) \\ (d_1) + (a_2, b_2, c_2) &= (d_1, a_2 + b_2, c_2) \\ (d_1) \times (a_2, b_2, c_2) &= (d_1 \times a_2, b_2, c_2) \\ \end{align}$$

となる.