自动搬运

查看原文

来自洛谷，原作者为

	UltiMadow Well I do.

搬运于2025-08-24 22:46:12，当前版本为作者最后更新于2023-04-10 19:24:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑对于单独的一个数列应该怎么做。

记字符串 bessie 为 $T$，为了方便，$T$ 的下标从 $0$ 开始。

考虑一个 dp：记 $f_{i,j}$ 为考虑前 $i$ 个字符，下一个需要匹配的是 $T$ 的第 $j$ 位的后缀个数。

那么有转移：$f_{i-1,j}\to f_{i,(j+[s_i=T_j])\bmod 6}$，$1\to f_{i,[s_i=T_0]}$，$f_{i-1,5}[s_i=T_6]\to ans$。

考虑用 cdq 分治维护这个过程，记当前分治区间为 $[l,r]$，已经计算好了 $[l,mid],(mid,r]$ 的对答案的贡献，现在需要计算横跨 $mid$ 的所有子串对答案的贡献。

对于每个区间，记录 $nxt_i$ 表示进入这个区间时下一个需要匹配 $T_i$，离开这个区间时下一个需要匹配 $T_{nxt_i}$，$cnt_i$ 表示离开区间时下一个需要匹配 $T_i$ 的后缀个数，$co_i$ 表示进入区间时下一个需要匹配 $T_i$ 的字符串在当前区间中有多少个位置可以对答案产生贡献。

合并 $[l,mid],(mid,r]$ 两个区间时，对答案的贡献即为 $\sum cnt_{[l,mid],i}co_{(mid,r],i}$，$nxt,cnt,co$ 的合并都是容易的。

这个分治的过程显然可以用线段树维护，时间复杂度 $\mathcal O(|T|n\log n)$

code:

#include<bits/stdc++.h>
#define int long long
#define MAXN 200010
using namespace std;
const string base="bessie";
int n,Q;
char s[MAXN];
struct tnode{
	int nxt[6],cnt[6],co[6],sum;
	tnode(char c='#',int pos=0){
		memset(nxt,0,sizeof(nxt));memset(cnt,0,sizeof(cnt));
		memset(co,0,sizeof(co));sum=0;
		if(pos){
			for(int i=0;i<6;i++)nxt[i]=(c==base[i]?(i+1)%6:i);
			cnt[nxt[0]]=1;co[5]=(c=='e'?n-pos+1:0);
		}
	}
};
tnode operator+(tnode ql,tnode qr){
	tnode ret;ret.sum=ql.sum+qr.sum;
	for(int i=0;i<6;i++){
		ret.nxt[i]=qr.nxt[ql.nxt[i]];
		ret.cnt[i]+=qr.cnt[i];ret.cnt[qr.nxt[i]]+=ql.cnt[i];
		ret.co[i]=ql.co[i]+qr.co[ql.nxt[i]];
		ret.sum+=ql.cnt[i]*qr.co[i];
	}
	return ret;
}
struct Segtree{
	tnode t[MAXN<<2];
	void pushup(int p){t[p]=t[p<<1]+t[p<<1|1];}
	void build(int p,int l,int r){
		if(l==r)return (void)(t[p]=tnode(s[l],l));int mid=(l+r)>>1;
		build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
	}
	void update(int p,int l,int r,int pos,char d){
		if(l==r)return (void)(t[p]=tnode(d,l));
		int mid=(l+r)>>1;
		if(pos<=mid)update(p<<1,l,mid,pos,d);
		else update(p<<1|1,mid+1,r,pos,d);
		pushup(p);
	}
}T;
signed main(){
	scanf("%s%lld",s+1,&Q);n=strlen(s+1);
	T.build(1,1,n);
	printf("%lld\n",T.t[1].sum);
	while(Q--){
		int pos;char opt[2];scanf("%lld%s",&pos,opt);
		T.update(1,1,n,pos,opt[0]);
		printf("%lld\n",T.t[1].sum);
	}
	return 0;
}