AtCoder ABC #434 (Ｓｋｙ株式会社プログラミングコンテスト2025) : G - Keyboard

このテクは知らなかった。
https://atcoder.jp/contests/abc434/tasks/abc434_g

問題

1～9及びBで構成される文字列Sが与えられる。
以下のクエリに順次答えよ。

• Sの１文字を書き換える
• Sの部分列S[L...R]が指定される。文字1～9をキーボードの1～9、'B'をBackspaceとみなしたとき、この文字列の順でキーボードをタイプしたときに得られる整数値を998244353で割った余りを答えよ。

解法

SegTreeの各ノードに、先行する数字と直後のBackspaceの対を削除した後における、(先行するBの数, 整数の桁数, 整数の値)を載せる。
ただ、この状態で単純なノードの積を容易にとることができない。

f(n,d) := ノードnに対し、下d桁分の値
とし、これを求めることを考える。

• ノード(2n+1)がd桁以上なら、再帰的にf(2n+1,d)を求めればよい。
• そうでない場合、ノード(2n+1)がm桁、ノード(2n+1)で先行するBがb個として、(f(2n,d-m+b)-f(2n,b))/10^bを求めればよい。

const ll mo=998244353;
ll p10[(1<<23)+10];
ll r10[(1<<23)+10];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	ll dfs(int id,int len) {
		if(len==0) return 0;
		if(val[id][1]==len) return val[id][2];
		if(val[2*id+1][1]>=len) return dfs(2*id+1,len);
		int lef=len-val[2*id+1][1];
		
		// lef+b桁
		assert(lef+val[2*id+1][0]<=val[2*id][1]);
		ll lv=dfs(2*id,lef+val[2*id+1][0]);
		// 左の下bけたを取る
		ll bv=val[2*id][2]-(val[id][2]-val[2*id+1][2])*r10[val[2*id+1][1]]%mo*p10[val[2*id+1][0]]%mo;
		
		ll v=(lv-bv)*r10[val[2*id+1][0]]%mo*p10[val[2*id+1][1]]+val[2*id+1][2];
		return (v%mo+mo)%mo;
	}
	V comp(int lid,V l,V r){
		V m={0,0,0};
		if(l[1]<=r[0]) {
			m[0]=l[0]+r[0]-l[1];
			m[1]=r[1];
			m[2]=r[2];
		}
		else if(r[0]==0) {
			m[0]=l[0];
			m[1]=l[1]+r[1];
			m[2]=(l[2]*p10[r[1]]+r[2])%mo;
		}
		else {
			m[0]=l[0];
			m[1]=r[1]+l[1]-r[0];
			
			// 下b桁
			ll lv=dfs(lid,r[0]);
			// 左の下bけたを引いたもの
			ll bv=(l[2]-lv+mo)*r10[r[0]]%mo;
			m[2]=(r[2]+bv*p10[r[1]])%mo;
			
		}
		return m;
	};
	
	SegTree_ma(){val=vector<V>(NV*2);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0,0,0};
		if(x<=l && r<=y) return val[k];
		return comp(k*2, getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, char v) {
		entry += NV;
		if(v=='B') {
			val[entry]={1,0,0};
		}
		else {
			val[entry]={0,1,v-'0'};
		}
		while(entry>1) entry>>=1, val[entry]=comp(entry*2,val[entry*2],val[entry*2+1]);
	}
};
SegTree_ma<array<ll,3>,1<<23> st;

int N,Q;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=r10[0]=1;
	
	p10[1]=10;
	r10[1]=modpow(10);
	for(i=2;i<(1<<23)+5;i++) {
		p10[i]=p10[i-1]*p10[1]%mo;
		r10[i]=r10[i-1]*r10[1]%mo;
	}
	
	cin>>N>>Q>>S;
	FOR(i,N) {
		if(S[i]=='B') {
			st.val[(1<<23)+i]={1,0,0};
		}
		else {
			st.val[(1<<23)+i]={0,1,S[i]-'0'};
		}
	}
	for(i=(1<<23)-1;i>=1;i--) st.val[i]=st.comp(2*i,st.val[2*i],st.val[2*i+1]);
	
	while(Q--) {
		cin>>i>>x;
		if(i==1) {
			string c;
			cin>>c;
			st.update(x-1,c[0]);
		}
		else {
			cin>>y;
			auto p=st.getval(x-1,y,0);
			if(p[1]==0) cout<<-1<<endl;
			else cout<<p[2]<<endl;
		}
	}
	
}

まとめ

このテク使える問題良くあるのかな。