正題

題目鏈接:https://atcoder.jp/contests/abl

---

題目大意

$n$個數字開始全是$1$，要求支持

修改一個區間為一個數字（是$1～9$的數）

求所有數字串起來$\%998244353$

---

解題思路

其實就是第$i$個數字乘上$10^i$，我們考慮如何用線段樹維護這個東西，我們可以維護一個$s_x={\sum }_{i=1}^{x}10^i$，然后區間修改時我們就可以用$s$來計算這個位置的值。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10,XJQ=998244353; ll n,q,s[N]; ll lazy[N*4],t[N*4]; void Downdata(ll x,ll l,ll m,ll r){if(!lazy[x])return;ll val=lazy[x];lazy[x*2]=lazy[x*2+1]=lazy[x];t[x*2]=(s[m]-s[l-1]+XJQ)%XJQ*val%XJQ;t[x*2+1]=(s[r]-s[m]+XJQ)%XJQ*val%XJQ;lazy[x]=0;return; } void Change(ll x,ll L,ll R,ll l,ll r,ll val){if(L==l&&R==r){lazy[x]=val;t[x]=(s[R]-s[L-1]+XJQ)%XJQ*val%XJQ;return;}ll mid=(L+R)>>1;Downdata(x,L,mid,R);if(r<=mid)Change(x*2,L,mid,l,r,val);else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);t[x]=(t[x*2]+t[x*2+1])%XJQ; } int main() {scanf("%lld%lld",&n,&q);s[1]=1;for(ll i=2;i<=n;i++)s[i]=s[i-1]*10%XJQ;for(ll i=1;i<=n;i++){s[i]=(s[i]+s[i-1])%XJQ;Change(1,1,n,i,i,1);}while(q--){ll l,r,d;scanf("%lld%lld%lld",&l,&r,&d);l=n-l+1;r=n-r+1;swap(l,r);Change(1,1,n,l,r,d);printf("%lld\n",t[1]);}return 0; }

總結

以上是生活随笔為你收集整理的ATcoder-Replace Digits【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。