William The Oblivious 参考代码C++

#include 
#define ull unsigned long long
#define ll long long
#define P pair
#define pll pair
using namespace std;
const int N=1e5+10,MAXN=5e3+10,mod=1e9+7,INF=0x3f3f3f3f;
char s[N];
//初始点->a->b->c
//0 1 2 3
//看作一个自动机 区间[L,R]中dp[i][j]表示i->j的最小代价
//遇到就走，不能停， 起点在i，经过区间[L,R]，终点在j 
struct node {
	int Left,Right,dp[4][4];
}NODE[N<<2];
void init(int idx, char ch) {
	memset(NODE[idx].dp,0x3f,sizeof(NODE[idx].dp));
	for (int i=0; i<=3; i++) NODE[idx].dp[i][i]=0;
	if (ch=='a') {
		NODE[idx].dp[0][0]=1; //在起点0 遇到a必会从0->1，所以必须删掉这个a，才继续待在0状态 
		NODE[idx].dp[0][1]=0; //不需要删除，直接从0->1 
	} else if (ch=='b') {
		NODE[idx].dp[1][1]=1;
		NODE[idx].dp[1][2]=0;
	} else {
		NODE[idx].dp[2][2]=1;
		NODE[idx].dp[2][3]=0;
	}
}
void PushUp(int idx) {
	memset(NODE[idx].dp,0x3f,sizeof(NODE[idx].dp));
	for (int i=0; i<=3; i++) {
		for (int j=i; j<=3; j++) {
			for (int k=i; k<=j; k++) {
				NODE[idx].dp[i][j]=min(NODE[idx].dp[i][j],NODE[idx<<1].dp[i][k]+NODE[idx<<1|1].dp[k][j]);
			}
		}
	}
}
void build(int l, int r, int idx) {
	NODE[idx].Left=l,NODE[idx].Right=r;
	if (l==r) {
		init(idx,s[l]);
		return;
	}
	int m=(l+r)>>1;
	build(l,m,idx<<1),build(m+1,r,idx<<1|1);
	PushUp(idx);
} 
void Updata(int pos, int idx, char ch) {
	if (NODE[idx].Left==NODE[idx].Right) {
		init(idx,ch);
		return;
	}
	int m=(NODE[idx].Left+NODE[idx].Right)>>1;
	if (pos<=m) Updata(pos,idx<<1,ch);
	else Updata(pos,idx<<1|1,ch);
	PushUp(idx);
}
int main() {
	int n,m; scanf("%d%d",&n,&m);
    scanf("%s",s+1);
	build(1,n,1);
	while (m--) {
		int idx; char ch[2];
        scanf("%d%s",&idx,ch);
		s[idx]=ch[0];
		Updata(idx,1,ch[0]);
		int res=1e9;
		for (int i=0; i<3; i++) {
			res=min(res,NODE[1].dp[0][i]);
		}
		printf("%dn",res);
	}
	return 0;
}