E. William The Oblivious（线段树）

线段树）"/>

E. William The Oblivious（线段树）

题意：给定只包含abc的字符串 ，q次单点修改 每次修改后问 使得不包含abc为子序列的最小操作数是多少
设t[k].abc为不包含abc为子序列的最小操作数
得到以下状态转移

        t[k].a=t[k<<1].a+t[k<<1|1].a;t[k].b=t[k<<1].b+t[k<<1|1].b;t[k].c=t[k<<1].c+t[k<<1|1].c;t[k].ab=min(t[k<<1].ab+t[k<<1|1].b,t[k<<1].a+t[k<<1|1].ab);t[k].bc=min(t[k<<1].bc+t[k<<1|1].c,t[k<<1].b+t[k<<1|1].bc);t[k].abc=min({t[k<<1].abc+t[k<<1|1].c,t[k<<1].ab+t[k<<1|1].bc,t[k<<1].a+t[k<<1|1].abc});

//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
char s[maxn];
struct node
{int l,r;int a,b,c;int ab,bc;int abc;
} t[maxn*4];
void push_up(int k)
{if(t[k].l!=t[k].r){t[k].a=t[k<<1].a+t[k<<1|1].a;t[k].b=t[k<<1].b+t[k<<1|1].b;t[k].c=t[k<<1].c+t[k<<1|1].c;t[k].ab=min(t[k<<1].ab+t[k<<1|1].b,t[k<<1].a+t[k<<1|1].ab);t[k].bc=min(t[k<<1].bc+t[k<<1|1].c,t[k<<1].b+t[k<<1|1].bc);t[k].abc=min({t[k<<1].abc+t[k<<1|1].c,t[k<<1].ab+t[k<<1|1].bc,t[k<<1].a+t[k<<1|1].abc});}
}
void build(int l,int r,int k)
{t[k].l=l;t[k].r=r;if(l==r){if(s[l]=='a') t[k].a=1;if(s[l]=='b') t[k].b=1;if(s[l]=='c') t[k].c=1;return ;}int mid=(l+r)>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);push_up(k);
}
void update(int l,int r,int k,char ch)
{if(l>t[k].r||t[k].l>r) return ;if(l<=t[k].l&&t[k].r<=r){s[l]=ch;t[k].a=t[k].b=t[k].c=0;if(s[l]=='a') t[k].a=1;if(s[l]=='b') t[k].b=1;if(s[l]=='c') t[k].c=1;return ;}update(l,r,k<<1,ch);update(l,r,k<<1|1,ch);push_up(k);
}
signed main()
{IOSint n,q;cin>>n>>q;cin>>(s+1);build(1,n,1);while(q--){int pos;char ch;cin>>pos>>ch;update(pos,pos,1,ch);cout<<t[1].abc<<"\n";}
}