学步园

//简单树状数组题

#include<stdio.h>
#include<string.h>
int n;
int c[50002];
void insert(int k,int dir)//改变第K项的值
{
    while(k<n+1)
    {
        c[k]+=dir;
        k+=k&(-k);//从C[k]往根节点一路上溯
    }
}
int sum(int k)
{
      int sm=0;
      while(k>0)
      {
          sm=sm+c[k];
          k-=k&(-k);//从C[k]往根节点一路下溯
      }
      return sm;
}
int main()
{
    int i,y,t,m,k,x,j=1;
    char str[50002],ch;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(c,0,sizeof(c));
        scanf("%s",str+1);
        for(i=3;i<=n;i++)
        {
            if(str[i]=='w')
            {
                if(str[i-1]=='b'&&str[i-2]=='w')
                    insert(i,1);
            }
        }
        printf("Case %d:\n",j++);
        for(i=0;i<m;i++)
        {
            scanf("%d",&k);
            if(k==0)
            {
                scanf("%d%d",&x,&y);x++;y++;
                if(y-x<2)   printf("0\n");
                else
                 printf("%d\n",sum(y)-sum(x+1));//从x到y,不包括x

            }
            else 
            {
                scanf("%d %c",&x,&ch);x++;
                if(ch==str[x])continue;            
                if(ch=='b')
                {
                    if(x-2>=1&&str[x-1]=='b'&&str[x-2]=='w')
                        insert(x,-1);                    
                    if(x-1>0&&x+1<=n&&str[x-1]=='w'&&str[x+1]=='w')
                        insert(x+1,1);
                    if(x+2<=n&&str[x+1]=='b'&&str[x+2]=='w')
                        insert(x+2,-1);
                }
                else 
                {
                    if(str[x-1]=='b'&&str[x-2]=='w'&&x-2>0)
                        insert(x,1);                    
                    if(str[x-1]=='w'&&str[x+1]=='w'&&x-1>0&&x+1<=n)
                        insert(x+1,-1);
                    if(str[x+1]=='b'&&str[x+2]=='w'&&x+2<=n)
                        insert(x+2,1);
                }
                str[x]=ch;
            }
        }            
    }
    return 0;
}