Codeforces #423 Div1 C. DNA Evolution

こちらも割とあっさり。
http://codeforces.com/contest/827/problem/C

問題

DNAよろしくATGCの4種類の文字で構成された文字列Sが与えられる。
以下のクエリを順次処理せよ。

• Sの1文字を差し替える。
• S部分文字列のS[L...R]に対し、入力文字列Tを同じ長さになるまで繰り返した文字列T'を考える。S[L...R]とTの同じ位置で一致する文字列はいくつあるか答える。

解法

T[i]と同じ文字がS[L+i],S[L+|T|+i],S[L+2|T|+i],S[L+3|T|+i],...にいくつあるかを高速に数えたい。

Tの長さが高々10であることを利用し、いくつかのBITを使おう。
BIT(p,m,c) := S[i]=cかつi mod p = mであるような場合、i番目の要素が1とみなされるような累積を持つBIT
1≦p≦10、0≦m＜p、cは4通りなので220個BITを準備する。

前者のクエリに対しては、i mod p=mとなる40個のBITを更新する。
後者のクエリについては、T[i]の値に応じて|T|個のBITの値を見ればよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,18> bt[10][10][4];

string S,T;
int N,Q;

string conv(string s) {
	FORR(c,s) {
		if(c=='A') c=0;
		if(c=='T') c=1;
		if(c=='G') c=2;
		if(c=='C') c=3;
	}
	return s;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	S=conv(S);
	
	FOR(i,N) {
		for(x=1;x<=10;x++) {
			bt[x-1][(i+1)%x][S[i]].add(i+1,1);
		}
	}
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>i>>T;
			T=conv(T);
			for(x=1;x<=10;x++) {
				bt[x-1][i%x][S[i-1]].add(i,-1);
				bt[x-1][i%x][T[0]].add(i,1);
			}
			S[i-1]=T[0];
		}
		else {
			int L,R;
			cin>>L>>R>>T;
			T=conv(T);
			int ret=0;
			FOR(x,T.size()) {
				ret += bt[T.size()-1][(L+x)%T.size()][T[x]](R)-bt[T.size()-1][(L+x)%T.size()][T[x]](L-1);
			}
			
			cout<<ret<<endl;
		}
	}
	
	
}

まとめ

Tの最大長が小さいことに気が付けば何とか。