\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
Lazy segtree. 文字列を 10進数とみなすので，segtree に乗せる． 区間の書き換えを保留しておくのがポイント．
Segtree の積が，文字列の結合に対応する． 10進数で考えるので，結合する前の桁数を持っておく必要がある． よって，segtree に乗せるデータは (10進数とみなしたときの値 \(x\) , 桁数 \(w\) ) で良い．
書きかえクエリのため，\(w\) 桁を \(d\) に変える処理が必要． つまり，\(d\cdots d\) が欲しい． これは \(d \cdot 1 \cdots 1 = d \cdot (10^{w}-1)/9\) と書ける．
実装
計算するときには \(w\) のまま使うことはなく， \(10^{w}\) だけあれば十分なので，この形で保持する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct S{
// x : k 桁
// p = 10^k
mint x, p;
S(){
x = 0;
p = 1;
}
S(mint x, mint p): x(x), p(p){}
};
S op (S a, S b){
return S( a.x * b.p + b.x, a.p * b.p);
}
S e(){ return S(); }
S mapping(mint f, S x){
if(f == 0) return x;
else return S(f * (x.p - 1)/9, x.p);
}
mint composition (mint f, mint g){
if(f == 0) return g;
else return f;
}
mint id(){ return 0; }
int main() {
ll n, q;
cin >> n >> q;
lazy_segtree<S, op,e, mint, mapping, composition, id> t(n);
rep(i,n){
t.set(i, S(1,10));
}
rep(i,q){
ll l,r,d; cin >> l >> r >> d;
--l;
t.apply(l,r,d);
cout << t.all_prod().x.val() << endl;
}
return 0;
}
