AT_abl_e Replace Digits 题解

分析

线段树模板题。

维护一个区间 \([l,r]\) 中 \(\sum\limits_{i=l}^r 10^{n-i}\) 的答案。将某个区间 \([l,r]\) 全部修改成 \(x\) 之后的表示的数就是 \(x \times(\sum\limits_{i=l}^r 10^{n-i})\)。区间修改可以用线段树，用快速幂或者预处理弄出来 \(10^x\)，建树的时候就能把每个 \([l,r]\) 对应的 \(\sum\limits_{i=l}^r 10^{n-i}\) 求出来。

唯一的细节就是取模，尽量在每个加法或乘法中都进行一次取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second

const int N=2e5+10,p=998244353;
int n,m;
struct node{
	int l,r,_10,s,lz;
}tr[N<<2];

il int qmi(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%p;
		a=a*a%p,b>>=1;
	}
	return ans;
}

il void up(int now){tr[now].s=(tr[now<<1].s+tr[now<<1|1].s)%p;}
il void down(int now){
	if(tr[now].lz){
		tr[now<<1].lz=tr[now].lz,tr[now<<1|1].lz=tr[now].lz;
		tr[now<<1].s=tr[now<<1].lz*tr[now<<1]._10%p;
		tr[now<<1|1].s=tr[now<<1|1].lz*tr[now<<1|1]._10%p;
		tr[now].lz=0;
	}
}
il void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r;
	if(l==r){
		tr[now].lz=1,tr[now]._10=qmi(10,n-l),tr[now].s=tr[now].lz*tr[now]._10%p;
		return ;
	}
	int mid=l+r>>1;
	build(now<<1,l,mid),build(now<<1|1,mid+1,r);
	up(now),tr[now]._10=(tr[now<<1]._10+tr[now<<1|1]._10)%p;
}
il void insert(int now,int l,int r,int k){
	if(tr[now].l>=l&&tr[now].r<=r){
		tr[now].lz=k,tr[now].s=tr[now].lz*tr[now]._10%p;
		return ;
	}
	int mid=tr[now].l+tr[now].r>>1;
	down(now);
	if(l<=mid) insert(now<<1,l,r,k);
	if(mid<r) insert(now<<1|1,l,r,k);
	up(now);
}
il int query(int now,int l,int r){
	if(tr[now].l>=l&&tr[now].r<=r) return tr[now].s;
	int mid=tr[now].l+tr[now].r>>1,ans=0;
	down(now);
	if(l<=mid) ans=(ans+query(now<<1,l,r))%p;
	if(mid<r) ans=(ans+query(now<<1|1,l,r))%p;
	up(now);
	return ans;
}

il void solve(){
	cin>>n>>m;
	build(1,1,n);
	for(re int i=1;i<=m;++i){
		int l,r,x;cin>>l>>r>>x;
		insert(1,l,r,x);cout<<query(1,1,n)<<"\n";
	}
}

signed main(){
	solve();
	return 0;
}