\(s_i\) が数字であるようなインデックスのみを抜き出して考えます。 また、それらに対して、\(t_i\) を \(s_i\) の直前の演算子を表したものとします。 ただし、直前の文字が存在しない場合や数字の場合には、演算子は空欄として扱います。

このようにしてできた \((s_i, t_i)\) の列を新たに \((A_i)_i\) と呼びます。

部分列として考える必要があるのは、\(A\) の部分列だけです。

目標は、\(A[l : r)\) に対応する値を行列で表現することです。 つまり、\(\text{make}(x)\) を \((s, t)\) を行列に移す写像として、

\[\text{make}(A_{r - 1}) \ldots \text{make}(A_{l + 1}) \text{make}(A_l)\]

のどこかの項が \(A[l : r)\) の値に対応しているような写像が作れれば良いです。

今、見ている部分列が \(X + Y_1 \times Y_2 \times \ldots Y_m \times Y\) として表されているとします。 このとき、

\(ans = X + Y_1 \times \ldots \times Y_m \times Y\)

\(tmp = Y_1 \times \ldots \times Y_m \times Y\)

\(factor = Y_1 \times \ldots \times Y_m\)

と定義すれば、(定数項 1を付け加えた) \(4 \times 4\) 行列を上手く定義することができます。 具体的な構成は演習としますが、必要ならば回答例を参考にしてください。 (https://atcoder.jp/contests/abc338/submissions/60892482)

行列表現さえわかれば、左から順に suffix sum を維持しながら求めていくことで簡単に \(O(N)\) で答えを求めることができます。