学步园

http://acm.hdu.edu.cn/showproblem.php?pid=4046

去年北京网络赛的一个题目，水题一枚

线段树和树状数组都可以的样子，我是用的树状数组，代码很戳

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
const int maxn=50010;

#define lowbit(x) x&(-x)

int d[maxn],n,m,pre[maxn];
char s[maxn];

void add(int p,int val)
{
    for(int i=p;i<=n;i+=lowbit(i))
      d[i]+=val;
}
int query(int p)
{
    int sum=0;
    for(int i=p;i>0;i-=lowbit(i))
      sum+=d[i];
    return sum;
}
int main()
{
    int ca,cas=1,a,b,c,p;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d%d",&n,&m);
        scanf("%s",s);
        memset(d,0,sizeof(d));
        memset(pre,0,sizeof(pre));
        for(int i=0;i<n-2;i++)
            if(s[i]=='w'&&s[i+1]=='b'&&s[i+2]=='w') add(i+1,1),pre[i+1]=1;
        printf("Case %d:\n",cas++);
        while(m--)
        {
            scanf("%d",&p);
            if(p==0)
            {
                scanf("%d %d",&a,&b);
                a++,b++;
                if(a+2>b) puts("0");
                else
                {
                    int sum1=query(b-2),sum2=query(a-1);
                    printf("%d\n",sum1-sum2);
                }
            }
            else
            {
                char ord[5];
                scanf("%d %s",&a,ord);
                s[a]=ord[0];
                for(int i=0;i<3;i++)
                  if(a-i>=0)
                  {
                      if(s[a-i]=='w'&&s[a-i+1]=='b'&&s[a-i+2]=='w')
                      {
                          if(!pre[a-i+1]) { add(a-i+1,1);pre[a-i+1]=1; }
                      }
                      else
                      {
                          if(pre[a-i+1]) { add(a-i+1,-1);pre[a-i+1]=0; }
                      }
                  }
            }
        }
    }
    return 0;
}