この問題は色々な解法が考えられます。\(N\) が \(10^5\) オーダーであれば平方分割を用いた解法が有力ですが、今回の \(N \leq 8 \times 10^6\) という制約下では実行時間制限が極めて厳しいため通すことは困難でしょう。また、セグメント木に永続平衡二分木を載せるという面白い解法も存在して、適切な工夫と実装によりこの解法でも通すことが出来るのでデータ構造に詳しい方は挑戦してみてください。
さて、この解説では、簡単に説明すると、一見するとマージできないデータ同士をマージすることができる面白いセグメント木 を用いた解法を説明します。セグメント木解法を考えたけれどマージが上手くいかなかった方は是非読んでみてください。

以降では文字列と呼んだ時 1, 2, 3, 4,5, 6, 7, 8, 9, B からなる文字列を指します。

はじめに、通常のセグメント木を用いた TLE 解法を説明します。
文字列 \(S\) に対して \(\mathrm{normalize}(S)\) を次のように定義します：

• \(S\) から (数字)+B という形の部分文字列を自由な順番で取り除けるだけ取り除いた時の最終的な \(S\) を \(\mathrm{normalize}(S)\) とする。

例えば \(S=\) 1BB234B567 のとき \(\mathrm{normalize}(S)=\) B23567 です。このとき \(S\) に対して \(\mathrm{normalize}(S)\) を 「\(S\) を正規化した文字列」と呼ぶことにします。
\(\mathrm{normalize}(S)\) に関して以下の事実が成り立つことが確認できます。

• \(\mathrm{normalize}(S)\) から先行する B を全て取り除いて得られる数列は \(f(S)\) と一致する。(言い換えると、\(\mathrm{normalize}(S)\) から求めたい答え \(f(S)\) を得られる。)
• 正規化された文字列 \(S, T\) に対して \(S \oplus T := \mathrm{normalize}(S+T)\) と \(\oplus\) を定義した時に、集合を正規化された文字列の集合、\(\oplus\) を二項演算、空文字列を単位元とするモノイドが構成出来る。
• 任意の文字列 \(S, T\) に対して \(\mathrm{normalize}(S+T) = \mathrm{normalize}(\mathrm{normalize}(S) + \mathrm{normalize}(T))\) が成り立つ。

このことから、セグ木の各区間に \(\mathrm{normalize}(S)\) を載せる解法が従います。しかしこの解法は当然ながら TLE してしまいます。理由としては、

• \(\mathrm{normalize}(S)\) の長さは最悪 \(N\) であるため、区間同士の積や区間総積クエリの計算に \(\mathrm{\Omega}(N)\) かかってしまう

という点が挙げられます。

この問題を解消するために、\(\mathrm{normalize}(S)\) の情報を必要最小限だけ持つことにしましょう。具体的には、次の 3 個の情報を持つ Data 型を考えます。

• \(b\) : \(\mathrm{normalize}(S)\) の先行する B の個数
• \(l\) : \(\mathrm{normalize}(S)\) から B を取り除いた時の文字列の長さ(すなわち \(f(S)\) の長さ)
• \(x\) : \(\mathrm{normalize}(S)\) から B を取り除いた時の文字列を 10 進数とみなした時の値 \(\text{mod }998244353\) (すなわち \(f(S)\) の値)

例えば \(\mathrm{normalize}(S)=\) BB12456 のとき \(b=2, l=5, x=12456\) となります。

このように情報を捨象した Data 型は空間 \(\mathrm{O}(1)\) で済むようになったため上述の問題は解消しましたが、代わりに Data 型同士の積の計算が不可能になったという欠点があります。例えば B1234567891 と BBBBBBB456 の積は B123456 ですが、これを Data 型 \((1,10,236323538), (7,3,456)\) に変換してしまうと Data 型同士の積が定義できなくなってしまっていることがわかります。(\((1,10,236323538)\) という値から 「B1234567891 の末尾 \(7\) 桁は 4567891 である」という情報が欠落しているため。)

このように情報を削りすぎて積の計算が不可能になると、モノイドではなくなりセグメント木に載らなくなるというのが一般論です。ところが実は、今回に限っては 左側のデータがセグメント木の上に載っていれば、Data 型同士の積が \(\mathrm{O}(\log N)\) でできる という点がこの問題の主眼点です。

積が計算可能なカラクリとしては、セグメント木の上に載っている Data 型はマージ過程がセグメント木として保存されているため、その情報をたどって詳細な情報を調査できる点にあります。
Data 型のデータ \(d_1\) がセグメント木上のある頂点に載っているとします。この時、任意の \(n\) に対して 「\(d_1\) に対応する文字列の末尾 \(n\) 桁の整数 \(\text{mod }998244353\)」 がわかれば、データ型 \(d_2\) に対して \(d_1\) と \(d_2\) の積が計算できます。そして、「\(d_1\) に対応する文字列の末尾 \(n\) 桁の整数 \(\text{mod }998244353\)」は \(d_1\) の子頂点に載っているデータをもとにセグメント木内を二分探索すれば \(\mathrm{O}(d_1 から葉までの距離) = \mathrm{O}(\log N)\) で計算できます！詳しくは以下に説明した疑似コードの手順を参照してください。

# セグメント木の情報を管理する配列の i 番目に載ったデータに対応する文字列の末尾 n 桁の整数 mod 998244353 を得る関数
# i 番目に載ったデータの子の頂点の index (存在すれば) はそれぞれ 2i, 2i+1 とする
# また、TEN[i] = 10^i mod 998244353, ITEN[i] = 10^{-i} mod 998244353 とする。これらははじめに長さ N+1 だけ前計算しておく
def dfs(i, n):
  assert seg[i].l >= n
  if n == 0: return 0
  if seg[i].l == n: return seg[i].x
  # この時点で頂点 i の子頂点の存在が保証される

  # 右の子頂点の数字の個数が十分多ければそれを返せばよい
  if seg[2 * i + 1].l >= n: return dfs(2 * i + 1, n)

  # そうでない場合は m 桁ほしい
  m = n - seg[2 * i + 1].l
  # しかし seg[2 * i] の情報は末尾 b 桁が seg[2 * i + 1] の B と打ち消されている
  b = seg[2 * i + 1].b
  # よって m+b 桁計算して下 b 桁を消す必要がある
  y = dfs(2 * i, m + b)
  # 打ち消された下 b 桁の情報を復元する
  z = seg[2 * i].x - (seg[i].x - seg[2 * i + 1].x) * ITEN[seg[2 * i + 1].l] * TEN[b]

  return (y - z) * ITEN[b] * TEN[seg[2 * i + 1].l] + seg[2 * i + 1].x

上記のコードを内部で呼ぶことで、左側のデータがセグメント木上に載っている時のデータ同士の積が \(\mathrm{O}(\log N)\) で計算できます。よってセグメント木に対する全てのクエリが \(\mathrm{O}(\log^2 N)\) でできるようになりました。
セグメント木の初期化の部分では \(\log\) がつかずに \(\mathrm{O}(N)\) でできるので (理由は読者への課題とします。計算量解析の練習です) 、この問題を \(\mathrm{O}(N + Q \log^2 N)\) で解くことが出来て、これは十分高速です。

• 関連文献：yosupo さんの記事