ABL E. Replace Digits

問題

長さNの文字列Sがあり、すべての文字は「1」になっている。
Q回、整数L, Rと数字Dが与えられるのでいかに答えよ。

• L番目からR番目の文字をすべてDに書き換え、文字列Sを10進数で書いた整数とみなした値を998,224,353で割ったあまりで表示せよ

制約

• 1 <= N, Q <= 200,000
• 1 <= L <= R <= N
• 1 <= D <= 9

解法

範囲更新、範囲取得したいので、遅延セグメント木の適用を考える。

ある範囲の文字列を10進数で表示してmodをとったものaを考える。
隣り合う範囲のaとa'は、その位置関係で連結した場合、aを10^{a'の範囲の長さ}倍したものとa'を合わせれば求められる。
したがって、モノイドとしては、「その範囲の数字列を10進数とみなしてmodをとった値」と「範囲の長さ」を保持すれば良い。

struct S { mint a; int size; }
S op(S l, S r) {
  mint x = mint(10).pow(r.size);
  return S{l.a*x+r.a, l.size+r.size};
}
S e(){
  return S{0,0};
}

これで、表示する答えは、seg.all_prod().a.val()で取得できる。

次に、範囲更新を考える。
「L～Rの数字をDに書き換える」ので、
あるモノイドSに作用させた場合、サイズは変わらず、S.aは1111....11111にDをかけたものになる。
作用素F'に作用素Fが作用した場合は、後に適用したほうのものになってほしいので、作用素に適用タイミングiをもたせて、それが大きい(後で更新したほう)にする。

struct F { int a, i; };
S mapping(F l, S r){
  if(l.i == -1) return r;
  return S{ones[r.size] * l.a, r.size};
}
F composition(F l, F r){
  if(l.i < r.i) return r;
  return l;
}
F id(){ return F{0, -1}; }

あとは、クエリごとに、seg.apply()してからseg.all_prod().a.val()を表示すればよい。