CF1380F.Strange Addition（线段树维护矩阵乘法）

//线段树维护矩阵乘法 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+100;
const int mod=998244353;
typedef long long ll;
struct node {
    ll sum[2][2];
    int l,r;
}segTree[maxn*4];
void update (int x) {
    segTree[x].l=segTree[x<<1].l;
    segTree[x].r=segTree[x<<1|1].r;
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++) {
            segTree[x].sum[i][j]=segTree[x<<1].sum[i][1]*segTree[x<<1|1].sum[1][j]%mod;
            int y=segTree[x<<1].r*10+segTree[x<<1|1].l;
            if (y>=10&&y<=18) {
                segTree[x].sum[i][j]+=segTree[x<<1].sum[i][0]*segTree[x<<1|1].sum[0][j]%mod*(9-(y-9)+1)%mod;
                if (segTree[x].sum[i][j]>=mod) segTree[i].sum[i][j]%=mod; 
            }
        }
}
ll a[maxn];
void build (int x,int l,int r) {
    if (l==r) {
        segTree[x].l=segTree[x].r=a[l];
        segTree[x].sum[1][1]=segTree[x].l+1;
        segTree[x].sum[0][0]=0;
        segTree[x].sum[0][1]=segTree[x].sum[1][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    update(x);
} 
void modify (int x,int l,int r,int pos,int d) {
    if (l==r) {
        segTree[x].l=segTree[x].r=d;
        segTree[x].sum[1][1]=segTree[x].l+1;
        segTree[x].sum[0][0]=0;
        segTree[x].sum[0][1]=segTree[x].sum[1][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    if (mid>=pos)
        modify(x<<1,l,mid,pos,d);
    else
        modify(x<<1|1,mid+1,r,pos,d);
    update(x);
}
int n,m,x,y;
string s;
int main () {
    scanf("%d%d",&n,&m);
    cin>>s;
    for (int i=0;i<s.length();i++) a[i+1]=s[i]-‘0‘;
    build(1,1,n);
    while (m--) {
        scanf("%d%d",&x,&y);
        modify(1,1,n,x,y);
        printf("%lld\n",segTree[1].sum[1][1]);
    }
}