E. William The Oblivious

William The Oblivious"/>

E. William The Oblivious

E. William The Oblivious

[链接](E. William The Oblivious)
题意:给你一个长为 n 的字符串，只包含 abc 三种字符。q 次操作，每次把一个位置的字符改成给定字符，询问当前串至少修改几次满足不包含子串 abc。修改指把一个位置的字符修改成 a、b、c 三种字符之一。
线段树维护
记录每个区间有多少a b c ab bc abc
维护区间
a = la + ra ;
b = lb + rb ;
c = lc + rc ;
ab = min(la + rab , lab + rb )
bc = min(lb + rbc , lbc + rc )
abc = min(la + rabc , lab + rbc , labc + rc )
后三个(删除区间中最小的字符个数以保证当前区间没有ab , bc , abc )
代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+10 ; 
struct node 
{int l ,r ; int a , b , c ; int ab , bc , abc  ;
}tr[N * 4 ] ;int n , q ;  
char str[N] ; void push_up(int u ) {tr[u].a = tr[u << 1 ].a + tr[u << 1 | 1 ].a;tr[u].b = tr[u << 1 ].b + tr[u << 1 | 1 ].b;tr[u].c = tr[u << 1 ].c + tr[u << 1 | 1 ].c;tr[u].ab = min(tr[u << 1 ].a + tr[u << 1 | 1].ab , tr[u << 1 ].ab + tr[u << 1 | 1 ].b); tr[u].bc = min(tr[u << 1 ].b + tr[u << 1 | 1].bc , tr[u << 1 ].bc +tr[u << 1 | 1 ].c) ;tr[u].abc = min({tr[u << 1 ].a + tr[u << 1 | 1].abc , tr[u << 1 ].ab + tr[u << 1 | 1].bc,tr[u << 1 ].abc + tr[u << 1 | 1 ].c}) ; }void build(int u , int l , int r ) {if(l == r ) {tr[u] = {l ,r } ; if(str[l] =='a') tr[u].a = 1 ; if(str[l] =='b') tr[u].b = 1 ; if(str[l] == 'c') tr[u].c = 1 ; return  ; }tr[u]= {l , r} ; int mid = l + r >> 1 ; build(u << 1 , l , mid ) , build(u << 1 | 1 , mid + 1 ,r ) ; push_up(u) ; }
void modify(int u , int id , char k ) {if(tr[u].l == id && tr[u].r == id) {tr[u].a = tr[u].b = tr[u].c = 0 ;if(k =='a') tr[u].a = 1 ; if(k =='b') tr[u].b = 1 ; if(k == 'c') tr[u].c = 1 ; return ; }int mid = tr[u].l + tr[u].r >> 1 ; if(id <= mid ) modify(u << 1 , id , k ) ;else modify(u << 1|1 , id , k ) ;push_up(u) ; 
}int main(){cin>>n>>q;scanf("%s" , str + 1 ) ; build(1 , 1 , n ) ; while(q-- ){int id ;char k ;cin>>id >>k ; modify(1 , id , k ) ;  cout<<tr[1].abc <<endl; }return 0 ; 
}