yukicoder : No.2554 MMA文字列2 (Query Version)

なんでMMAなんだろうな。
https://yukicoder.me/problems/no/2554

問題

MMA文字列とは、アルファベット3文字からなる文字列で、前2文字が一致し、末尾1文字がそれとは異なるものをいう。
文字列Sに対し、以下のクエリに答えよ。

• Sの1文字を更新する
• Sの部分文字列S[L...R]が指定される。このうちの連続とは限らない3文字の部分文字列のうち、MMA文字列の数を答える。

解法

SegTreeを使い、各ノードに以下53要素の配列を持たせよう。

• 各アルファベットの登場回数を保持
• MA型の部分文字列の登場回数を、M側の文字種毎に保持
• MMA型の部分文字列の登場回数

あとはSegTreeの1点更新と区間内のMMA文字列の登場回数算出を処理していく。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		V a;
		int i,j;
		ll rs=0;
		FOR(i,53) a[i]=l[i]+r[i];
		FOR(i,26) rs+=r[i];
		FOR(i,26) {
			//M + MA
			a[52]+=l[i]*r[26+i];
			//M + A
			a[i+26]+=l[i]*(rs-r[i]);
			//MM + A
			a[52]+=l[i]*(l[i]-1)/2*(rs-r[i]);
		}
		return a;
	};
	
	SegTree_1(){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 V();
		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, char v) {
		entry += NV;
		int i;
		FOR(i,53) val[entry][i]=0;
		val[entry][v-'A']=1;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<array<ll,53>,1<<17> st;

int N;
string S;
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) st.update(i,S[i]);
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>s;
			st.update(x-1,s[0]);
		}
		else {
			cin>>x>>y;
			auto a=st.getval(x-1,y);
			cout<<a[52]<<endl;
		}
	}
	
	
}

まとめ

最初雑にSegTreeのサイズ取ったらMLEになってしまった。