前置知识
解法
需要维护区间信息,考虑使用线段树维护。
预处理出 \(\overline{xx \dots x}\),其中 \(x \in \{1,2,3,4,5,6,7,8,9 \}\),便于区间赋值。
然后就是普通的线段树板子了。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=998244353;
ll mi[200010],num[12][200010];
struct SMT
{
struct SegmentTree
{
ll l,r,len,sum,lazy;
}tree[800010];
ll lson(ll x)
{
return x*2;
}
ll rson(ll x)
{
return x*2+1;
}
void pushup(ll rt)
{
tree[rt].len=tree[lson(rt)].len+tree[rson(rt)].len;
tree[rt].sum=(tree[lson(rt)].sum*mi[tree[rson(rt)].len]+tree[rson(rt)].sum)%p;
}
void build(ll rt,ll l,ll r)
{
tree[rt].l=l;
tree[rt].r=r;
tree[rt].lazy=0;
if(l==r)
{
tree[rt].len=tree[rt].sum=1;
return;
}
ll mid=(tree[rt].l+tree[rt].r)/2;
build(lson(rt),l,mid);
build(rson(rt),mid+1,r);
pushup(rt);
}
void pushdown(ll rt)
{
if(tree[rt].lazy!=0)
{
tree[lson(rt)].lazy=tree[rt].lazy;
tree[lson(rt)].sum=num[tree[rt].lazy][tree[lson(rt)].len];
tree[rson(rt)].lazy=tree[rt].lazy;
tree[rson(rt)].sum=num[tree[rt].lazy][tree[rson(rt)].len];
tree[rt].lazy=0;
}
}
void update(ll rt,ll x,ll y,ll val)
{
if(x<=tree[rt].l&&tree[rt].r<=y)
{
tree[rt].lazy=val;
tree[rt].sum=num[val][tree[rt].len];
return;
}
pushdown(rt);
ll mid=(tree[rt].l+tree[rt].r)/2;
if(x<=mid)
{
update(lson(rt),x,y,val);
}
if(y>mid)
{
update(rson(rt),x,y,val);
}
pushup(rt);
}
pair<ll,ll> query(ll rt,ll x,ll y)
{
if(x<=tree[rt].l&&tree[rt].r<=y)
{
return make_pair(tree[rt].sum,tree[rt].len);
}
pushdown(rt);//以下部分在本题中显多此一举
ll mid=(tree[rt].l+tree[rt].r)/2;
pair<ll,ll>lp=make_pair(0,0),rq=make_pair(0,0);
if(x<=mid)
{
lp=query(lson(rt),x,y);
}
if(y>mid)
{
rq=query(rson(rt),x,y);
}
return make_pair((lp.first*mi[rq.second]%p+rq.first)%p,lp.second+rq.second);
}
}T;
int main()
{
ll n,q,l,r,x,i,j;
cin>>n>>q;
mi[0]=1;
for(i=1;i<=n;i++)
{
mi[i]=mi[i-1]*10%p;
for(j=1;j<=9;j++)
{
num[j][i]=(num[j][i-1]*10+j)%p;
}
}
T.build(1,1,n);
for(i=1;i<=q;i++)
{
cin>>l>>r>>x;
T.update(1,l,r,x);
cout<<T.query(1,1,n).first<<endl;
}
return 0;
}
标签:Digits,rt,lazy,题解,ll,abl,tree,len,rson
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18343910