yukicoder : No.3239 Omnibus

時間に間に合わず…。
https://yukicoder.me/problems/no/3239

問題

3文字以上の文字列Xの略語とは、末尾3文字を挿す。
文字列Sが与えられるので、以下のクエリを順次答えよ。

• Sの1文字を指定した文字に上書きする。
• Sの部分列S[L..R]と略語Aが指定される。S[L..R]の部分列のうち、略語がAとなるものはいくつあるか。

解法

以下の値を考える。
num(i,a) := S[i]+S[i+1]+S[i+2]がaと一致するなら1しないなら0
sum(i,a) := S[i]+S[i+1]+S[i+2]がaと一致するならiしないなら0

上記2値のprefix sumを、aごとに保持しよう。
これは有効な要素のみ持つ動的BITで保持できる。
前者のクエリに対しては、上記BITを更新しよう。

後者については、num(i,a)=1となるL≦i≦R-2に対し、sum(i,a)-(L-1)の総和を取ればよいので、上記BITを使い計算しよう。

template<class V, int ME> class BIT_map {
public:
	map<int,V> bit;
	V op(V a,V b){ return a+b; };
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s=op(s,bit[e-1]),e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]=op(bit[e-1],v),e+=e&-e;}
};

BIT_map<int,18> num[26*26*26];
BIT_map<ll,18> sum[26*26*26];

int N,Q;
int V[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>s;
	FOR(i,N) V[i]=s[i]-'a';
	FOR(i,N) {
		x=V[i]+V[i+1]*26+V[i+2]*26*26;
		num[x].add(i,1);
		sum[x].add(i,i);
	}
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>s;
			x--;
			for(i=max(0,x-2);i<=x;i++) {
				y=V[i]+V[i+1]*26+V[i+2]*26*26;
				num[y].add(i,-1);
				sum[y].add(i,-i);
			}
			V[x]=s[0]-'a';
			for(i=max(0,x-2);i<=x;i++) {
				y=V[i]+V[i+1]*26+V[i+2]*26*26;
				num[y].add(i,1);
				sum[y].add(i,i);
			}
		}
		else {
			int L,R;
			cin>>L>>R>>s;
			L--;
			y=(s[0]-'a')*1LL+(s[1]-'a')*26LL+(s[2]-'a')*26LL*26;
			ll ret=0;
			if(R-L>=3) {
				ll ns=num[y](R-3)-num[y](L-1);
				ll ss=sum[y](R-3)-sum[y](L-1);
				ret=ss-ns*(L-1);
			}
			cout<<ret<<endl;
		}
	}
	
}

まとめ

動的BITを久々に使った。