思路

首先考虑没有多次修改的情况。

不难证明对于 bessie 一个字符串，我们可以从某个位置依次向后找接下来的字符。所以我们可以枚举每个子串 $s_i\sim s_j$，先预处理出每个位置后面的第一个 b,e,s,i，然后 $O(n)$ 计算出现次数即可。复杂度 $O(n^3)$。

考虑如何优化，我们可以只枚举左端点，向右枚举的时候维护从 $s_i\sim s_j$ 中 bessie 出现的次数，然后累加即可。复杂度 $O(n^2)$。

考虑如何优化，计 $dp_{i,0\sim5}$ 表示以 $i$ 为后缀的字符串中，匹配到 bessie 的前 $0\sim5$ 位的不同位置数量，同时维护 $sum$ 表示所有前面的方案中匹配数量的总和。如果接下来的第 $i+1$，$sum$ 可以加上 $dp_{i,5}$，其他情况依次转移即可。每个位置算完后将 $sum$ 累加到答案中即可。复杂度 $O(n)$。

如果加上修改呢？不难发现 $dp_{i,0\sim5},sum,ans$ 都是可线性递推的，不难想到可以将其转化成矩阵形式，维护以上 $3$ 个量，修改直接修改矩阵即可，用线段树维护（其实就是动态 dp）。复杂度 $O(qn\log n8^3)$，可以通过。

这题其实还可以区间修改和区间查询。

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
using namespace std;
struct mtx{
	int a[9][9];
};
mtx mul(mtx x,mtx y){
	mtx z; for(int i=0;i<9;i++) for(int j=0;j<9;j++) z.a[i][j]=0;
	for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(x.a[i][j]) for(int k=0;k<9;k++) z.a[i][k]+=x.a[i][j]*y.a[j][k];
	return z;
}
mtx makem(char c){
	mtx ret;
	for(int i=0;i<9;i++) for(int j=0;j<9;j++) ret.a[i][j]=0;
	ret.a[7][1]=1;
	ret.a[0][8]=1;
	ret.a[8][8]=1;
	if(c=='b'){
		ret.a[0][0]=1;
		ret.a[1][2]=1;
		ret.a[2][2]=1;
		ret.a[3][3]=1;
		ret.a[4][4]=1;
		ret.a[5][5]=1;
		ret.a[6][6]=1;
		ret.a[7][7]=1;
		return ret;
	}
	if(c=='e'){
		ret.a[0][0]=1;
		ret.a[1][1]=1;
		ret.a[2][3]=1;
		ret.a[3][3]=1;
		ret.a[4][4]=1;
		ret.a[5][5]=1;
		ret.a[6][0]=1;
		ret.a[6][8]=1;
		ret.a[6][1]=1;
		ret.a[7][7]=1;
		return ret;
	}
	if(c=='s'){
		ret.a[0][0]=1;
		ret.a[1][1]=1;
		ret.a[2][2]=1;
		ret.a[3][4]=1;
		ret.a[4][5]=1;
		ret.a[5][5]=1;
		ret.a[6][6]=1;
		ret.a[7][7]=1;
		return ret;
	}
	if(c=='i'){
		ret.a[0][0]=1;
		ret.a[1][1]=1;
		ret.a[2][2]=1;
		ret.a[3][3]=1;
		ret.a[4][4]=1;
		ret.a[5][6]=1;
		ret.a[6][6]=1;
		ret.a[7][7]=1;
		return ret;
	}
	ret.a[0][0]=1;
	ret.a[1][1]=1;
	ret.a[2][2]=1;
	ret.a[3][3]=1;
	ret.a[4][4]=1;
	ret.a[5][5]=1;
	ret.a[6][6]=1;
	ret.a[7][7]=1;
	return ret;
}
char c[200005];
struct sgt{
	mtx f[800005];
	void build(int i,int l,int r){
		if(l==r){
			f[i]=makem(c[l]);
			return ;
		}
		build(i*2,l,mid),build(i*2+1,mid+1,r);
		f[i]=mul(f[i*2],f[i*2+1]);
//		cout<<l<<" "<<r<<" "<<f[i].a[1][0]+f[i].a[7][0]<<" "<<f[i].a[1][8]+f[i].a[7][8]<<endl;
	}
	void change(int i,int l,int r,int pos){
		if(l==r){
			f[i]=makem(c[l]);
			return ;
		}
		if(pos<=mid) change(i*2,l,mid,pos);
		else change(i*2+1,mid+1,r,pos);
		f[i]=mul(f[i*2],f[i*2+1]);
	}
}tree;
mtx ori;
signed main(){
	ori.a[0][1]=ori.a[0][7]=1;
	string s; cin>>s; int n=s.size();
	for(int i=1;i<=n;i++) c[i]=s[i-1];
	tree.build(1,1,n);
	cout<<mul(ori,tree.f[1]).a[0][8]<<"\n";
	int q; cin>>q;
	while(q--){
		int pos; char cg;
		cin>>pos>>cg;
		c[pos]=cg;
		tree.change(1,1,n,pos);
		cout<<mul(ori,tree.f[1]).a[0][8]<<"\n";
	}
	return 0;
} 

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

记字符串 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;
}