codeforces：B. William the Vigilant（c语言题解）

题目出自：Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)的B题

题目简述：输入一个长度为n的只包含'a','b','c'的字符串，进行q次操作，每次就输入数字i和字符a，b，c中的一个，然后将原输入的字符串的第i个字符换成新输入的字符，再返回新的字符串中一共有多少组连在一起的abc

Input

The first line contains two integers nn and qq (1≤n,q≤105)(1≤n,q≤105), the length of the string and the number of queries, respectively.

The second line contains the string ss, consisting of characters "a", "b" and "c".

Each of the next qq lines contains an integer ii and character cc (1≤i≤n)(1≤i≤n), index and the value of the new item in the string, respectively. It is guaranteed that character's cc value is "a", "b" or "c".

Output

For each query output the minimal number of characters that would have to be replaced so that the string doesn't contain "abc" as a substring.

Example

input

9 10
abcabcabc
1 a
1 b
2 c
3 a
4 b
5 c
8 a
9 b
1 c
4 a

output

3
2
2
2
1
2
1
1
1
0

思路：一开始，我单纯用for循环去计算每3个字符是不是连着的abc，而且这个for循环是每输入一个样例就循环一次，所以exceed time。后面，先用一次循环把输入的字符串中abc的总数计算出来为d，因为他接下来每次只改变一个字符，那么我们就直接根据d再去做每一次的计算。

而是否超时，就看你每一次的样例怎么运算了。我是取目标第i个字符的前两个和后两个，共同组成5个字符（即a[i-3]到a[i+1]）(第i个是a[i-1])，然后判断这5个字符里面abc的数量。关于计算就是，拿d先减去没改变前a[i-3]到a[i+1]中abc的数量d1，再加上改变后a[i-3]到a[i+1]中abc的数量d2.

#include<stdio.h>
#include<string.h>
#include<math.h>
char a[100000],e[100000];
int main(){
int n,q,i,d1,d2,j; char b;
scanf("%d%d",&n,&q);
scanf("%s",a);

int d=0;
    char * p;
    memcpy(e,a,sizeof a);//这里我复制一个新的数组e
    while((p=strchr(e,'a'))!=NULL)//每次跳到'a'的位置去判断后面是不是bc
    {   *p='0'; //把计算过的a换成其他字符，就可以找下一个a
        if(*(p+1)=='b'&&*(p+2)=='c')d++;
    }
while(q--)
{    d1=0;d2=0;
    scanf("%d %c",&i,&b);
    for( j=i-3;j+2<=i+1;j++ )//注意：这里是j+2<=i+1,要判断的3个字符都在区间内
    {
        if((a[j]=='a')&&(a[j+1]=='b')&&(a[j+2]=='c')){d1++;break;}
    }
    
    a[i-1]=b;
    
    for(j=i-3;j+2<=i+1;j++ )
    {
        if((a[j]=='a')&&(a[j+1]=='b')&&(a[j+2]=='c')){d2++;break;}
    }
    
    d=d+d2-d1;
    
    printf("%d\n",d);
}
return 0;
}