【題解】AtCoder ACL Beginner Contest E – Replace Digits

#include <bits/stdc++.h>
using namespace std;

int n, q, l, r, d, lazy[200005<<2], mod = 998244353;
long long pre[200005], st[200005<<2];

void update(int x, int l, int r, int ul, int ur, int u){
    if (ul <= l && r <= ur){
        lazy[x] = u;
        st[x] = u*(pre[r]+mod-pre[l-1])%mod;
        return;
    }
    int mid = (l+r)/2;
    if (lazy[x]){
        lazy[x<<1] = lazy[x];
        lazy[x<<1|1] = lazy[x];
        st[x<<1] = lazy[x]*(pre[mid]+mod-pre[l-1])%mod;
        st[x<<1|1] = lazy[x]*(pre[r]+mod-pre[mid])%mod;
        lazy[x] = 0;
    }
    if (ul <= mid) update(x<<1, l, mid, ul, ur, u);
    if (mid < ur) update(x<<1|1, mid+1, r, ul, ur, u);
    st[x] = (st[x<<1]+st[x<<1|1]) % mod;
}

int main(){
    cin >> n >> q;
    pre[1] = 1;
    long long tmp = 1;
    for (int i = 2; i <= n; i++){
        tmp *= 10;
        tmp %= mod;
        pre[i] = (pre[i-1]+tmp) % mod;
    }
    update(1, 1, n, 1, n, 1);
    while (q--){
        cin >> l >> r >> d;
        update(1, 1, n, n+1-r, n+1-l, d);
        cout << st[1] << "\n";
    }
}