#include using namespace std; using ll = long long; using pi = pair; const int mx = 1'000'011; const int tmax = 1<<21; const int mod = 998'244'353; struct SegmentTree{ ll tree[tmax][10], lazy[tmax][10], st[tmax/2 + 1][10]; ll e[mx], f[10]; void init(int n, const vector&v){ for(int s=0; s> 1; build(n << 1, l, m); build(n << 1 | 1, m+1, r); for(int s=0; s<10; s++)tree[n][s] = merge(tree[n << 1][s], tree[n << 1 | 1][s], r - m); } ll merge(ll a,ll b,int bl){ bl = max(bl, 0); return ((a * e[bl]) % mod + b) % mod; } void propagate(int n,int l,int r){ bool flag = 1; for(int s=0; s<10; s++)if(lazy[n][s] != s)flag = 0; if(flag)return; if(l ^ r){ for(int nx : {n << 1, n << 1 | 1}){ for(int s=0; s<10; s++)f[s] = lazy[n][lazy[nx][s]]; for(int s=0; s<10; s++)lazy[nx][s] = f[s]; } } fill(f, f+10, 0); for(int s=0; s<10; s++){ f[lazy[n][s]] = (tree[n][s] + f[lazy[n][s]]) % mod; } for(int s=0; s<10; s++)tree[n][s] = f[s]; iota(lazy[n], lazy[n]+10, 0); } void update(int l,int r,int x,int fx,int n =1,int nl =1,int nr =tmax/2){ propagate(n, nl, nr); if(l > nr || r < nl)return; if(l <= nl && nr <= r){ lazy[n][x] = fx; propagate(n, nl, nr); return; } int m = (nl + nr) >> 1; update(l, r, x, fx, n << 1, nl, m); update(l, r, x, fx, n << 1 | 1, m+1, nr); for(int s=0; s<10; s++) tree[n][s] = merge(tree[n << 1][s], tree[n << 1 | 1][s], nr - m); } ll Q(int l,int r,int k,int n =1,int nl =1,int nr =tmax/2){ propagate(n, nl, nr); if(l > nr || r < nl)return 0; if(l <= nl && nr <= r)return tree[n][k]; int m = (nl + nr) >> 1; return merge(Q(l, r, k, n << 1, nl, m), Q(l, r, k, n << 1 | 1, m+1, nr), min(r, nr)-m); } ll query(int l,int r){ ll ans = 0; for(int s=0; s<10; s++){ ans += (Q(l, r, s) * s) % mod; ans %= mod; } return ans; } }ST; int main(){ cin.tie(0)->sync_with_stdio(0); string k; cin >> k; int sz = k.size(); vectorv(k.size() +1); for(int s=1; s<=sz; s++)v[s] = k[s-1] - '0'; ST.init(sz, v); int Q; cin >> Q; while(Q--){ int op, l, r, x, fx; cin >> op >> l >> r; if(op == 1){ cin >> x >> fx; ST.update(l, r, x, fx); }else cout << ST.query(l, r) << "\n"; } }

코드 #6176