AtCoder ACLBC : E - Replace Digits

普段のABCより少し難しめ？
https://atcoder.jp/contests/abl/tasks/abl_e

問題

N桁の整数があり、初期値で各桁は1である。
ここにQ個のクエリが与えられる。
各クエリでは、この整数のある連続した桁の区間の数値を指定された値Dで上書きする。

各クエリ後の整数の値を 998,244,353 で割った余りを求めよ。

解法

SegTreeを使い、各ノードに区間内の値を10進数とみなして998,244,353 で割った余りと桁数を持っておこう。
そうすればノード毎に子ノードの値を合成していくことができる。
区間更新を簡単にできるように、111....111を998244353で割った余りを事前に準備しておくとよい。

ll p1[2202020];
ll p10[2202020];
const ll mo=998244353;

template<class V,int NV> class SegTree_2 {
public:
	vector<V> sum,val;
	SegTree_2(){sum.resize(NV*2,0);val.resize(NV*2,0);};
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			sum[k]=v*p1[r-l]%mo;
			val[k]=v;
		}
		else if(l < y && x < r) {
			if(val[k]>=0) {
				val[2*k]=val[2*k+1]=val[k];
				sum[2*k]=sum[2*k+1]=val[k]*p1[(r-l)/2]%mo;
				val[k]=-1;
			}
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			sum[k]=(sum[2*k]+sum[2*k+1]*p10[(r-l)/2])%mo;
		}
	}
};
SegTree_2<ll,1<<20> st;
int N,Q,L,R,D;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,2201010) {
		p1[i+1]=(p1[i]*10+1)%mo;
		p10[i+1]=(p10[i]*10)%mo;
	}
	
	cin>>N>>Q;
	st.update(0,N,1);
	FOR(i,Q) {
		cin>>L>>R>>D;
		R=N-R;
		L=N-L;
		st.update(R,L+1,D);
		cout<<st.sum[1]<<endl;
	}
	
	
}

まとめ

これはよく見かけそうな問題。