cf1609E. William The Oblivious

William The Oblivious"/>

cf1609E. William The Oblivious

William The Oblivious

题意：
给一个仅含abc的字符串，每次操作可以修改某一位的字符。
每次操作后，要求输出最少删除多少个数可以使字符串中不含有子序列abc。

建立一个线段树， a [ ] , b [ ] , c [ ] , a b [ ] , b c [ ] , a b c [ ] a[],b[],c[],ab[],bc[],abc[] a[],b[],c[],ab[],bc[],abc[]代表使得区间中没有子序列a,b,c,ab,bc,abc最少删除的字符数。

a[o]=a[lson]+a[rson];
b[o]=b[lson]+b[rson];
c[o]=c[lson]+c[rson];
ab[o]=min(a[lson]+ab[rson],ab[lson]+b[rson]);
bc[o]=min(b[lson]+bc[rson],bc[lson]+c[rson]);
abc[o]=min(a[lson]+abc[rson],ab[lson]+bc[rson],abc[lson]+c[rson]);

#include<bits/stdc++.h>
using namespace std;#define N ((int)4e5)struct segment_tree{string s;int a[N],b[N],c[N],ab[N],bc[N],abc[N];#define lson (o*2)#define rson (o*2+1)#define mid ((l+r)>>1)void update(int o) {a[o]=a[lson]+a[rson];b[o]=b[lson]+b[rson];c[o]=c[lson]+c[rson];ab[o]=min(a[lson]+ab[rson],ab[lson]+b[rson]);bc[o]=min(b[lson]+bc[rson],bc[lson]+c[rson]);abc[o]=min(min(a[lson]+abc[rson],ab[lson]+bc[rson]),abc[lson]+c[rson]);return ;}void build(int o,int l,int r) {if(l==r) {if(s[l]=='a') a[o]=1,b[o]=0,c[o]=0;if(s[l]=='b') a[o]=0,b[o]=1,c[o]=0;if(s[l]=='c') a[o]=0,b[o]=0,c[o]=1;return ;}build(lson,l,mid),build(rson,mid+1,r);update(o);return ;}void change(int o,int l,int r,int L,int R,char d) {if(l>R||r<L) return ;if(l==r) {s[l]=d;if(s[l]=='a') a[o]=1,b[o]=0,c[o]=0;if(s[l]=='b') a[o]=0,b[o]=1,c[o]=0;if(s[l]=='c') a[o]=0,b[o]=0,c[o]=1;return ;}change(lson,l,mid,L,R,d),change(rson,mid+1,r,L,R,d);update(o);return ;}int query() {return abc[1];}
} tr;int main() {int n,m;cin>>n>>m>>tr.s;tr.s=" "+tr.s;tr.build(1,1,n);for(int i=1;i<=m;i++) {int x;char d;cin>>x>>d;tr.change(1,1,n,x,x,d);cout<<tr.query()<<endl;}return 0;
}