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 ;
}

最后

以上就是积极犀牛为你收集整理的E. William The ObliviousE. William The Oblivious的全部内容，希望文章能够帮你解决E. William The ObliviousE. William The Oblivious所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。