yukicoder : No.2762 Counting and Deleting

こちらは割とすんなりか。
https://yukicoder.me/problems/no/2762

問題

01で構成される文字列Sが与えられる。
以下のクエリに順次こたえよ。

• Sのうち指定された部分文字列を"_"で置き換える。
• Sのうち指定された部分文字列に対し、その部分列としてあり得る01で構成されるLeading Zeroを含まない文字列は何通りか。

解法

後者のクエリに対しては、SegTreeに3*3行列を乗せて行列乗算を行うことで、末尾が0なる部分列や1となる部分列の個数を数え上げられる。
前者のクエリに対し、1つの位置は2回以上置き換えても効果がないので、まだ置き換えてない位置をsetなどで管理し、それらに対しSegTreeの1点更新を行えばよい。

vector<ll> def={1,0,0,0,1,0,0,0,1};
vector<ll> A0={1,1,0,0,1,0,0,0,1};
vector<ll> A1={1,0,0,1,1,1,0,0,1};

const ll mo=998244353;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		vector<ll> A(9);
		int a,b,c;
		FOR(a,3) FOR(b,3) FOR(c,3) {
			(A[a*3+b]+=r[a*3+c]*l[c*3+b])%=mo;
		}
		
		return A;
	};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<vector<ll>,1<<20> st;

int N,Q;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	set<int> alive;
	FOR(i,N) {
		alive.insert(i);
		if(S[i]=='0') st.update(i,A0);
		else st.update(i,A1);
	}
	alive.insert(N);
	while(Q--) {
		int L,R;
		cin>>i>>L>>R;
		L--;
		if(i==1) {
			auto it=alive.lower_bound(L);
			while(*it<R) {
				st.update(*it,def);
				it=alive.erase(it);
			}
		}
		else {
			auto p=st.getval(L,R);
			cout<<(p[2]+p[5])%mo<<endl;
		}
	}
	
	
	
	
}

まとめ

部分列の数え上げを行列乗算とSegTreeでやるの、結構久々かも。