36th ACM AR Beijing Online Contest G题 Panda 线段树 树状数组

好多分支，枚举真的要十分仔细，注意解决问题的全面性！树状数组解决，效率还OK。

#include<stdio.h>
#include <string.h>

#define N 50010
int n, len, c[N];
char s[N];

int getLowBit(int n)
{
    return n&(-n);
}

void add(int i,int m)
{

    for(;i<=n;i+=getLowBit(i))
    {
       c[i]+=m;
    }
}

void sub(int i,int m)
{
    for(;i<=n;i+=getLowBit(i))
    {
       c[i]-=m;
    }
}

int getSum(int i)
{
    int sum=0;
    for(;i>0;i-=getLowBit(i))
    {
       sum+=c[i];
    }
    return sum;
}

int main()
{
    int m, i, a, b, t, num=0, cnt, j, tb,query, last, init;
    char *p;
    freopen("input","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
       scanf("%d%d",&n,&m);
       memset(c,0,sizeof(c));
       getchar(), gets(s);
       p = s, init = 1;;
       len = strlen(s);

       while(p =strstr(p,"wbw"))
       {

           add(last=p-s+1, 1);
           while(init < last)
           {
              add(init++, 0);
           }
           init = last + 1;
           p += 2;
       }
       while(init <= len)
       {
           add(init++, 0);
       }
       printf("Case%d:n",++num);
       for(i=0;i<m;i++)
       {
           scanf("%d %d",&query, &a);
           if(query == 0)
           {
              scanf("%d",&b);
              tb = getSum(b-1);
              if(b-a<2)
              {
                  printf("0n");
                  continue;
              }
              if(a==0)
              {
                  printf("%dn",tb);
              }
              else
              {
                  printf("%dn",tb- getSum(a));
              }
           }
           else
           {
              b = getchar();
              scanf("%c",&b);
              if(a==len-1 || a==0) //左或右没有，a在起始或末尾
              {
                  if(a==len-1 &&a!=0)//右没有，在起始
                  {
                     if(s[a-2]=='w'&& s[a-1]=='b' && s[a]=='w' && b=='b')//wbw
                     {
                         sub(a-1, 1);
                     }
                     else if(s[a-2]=='w'&& s[a-1]=='b' && s[a]=='b' && b=='w')//wbb
                     {
                         add(a-1, 1);
                     }
                  }
                  else if(a==0 &&a!=len-1)//左没有, 在末尾
                  {
                     if(s[a]=='w'&& s[a+1]=='b' && s[a+2]=='w' && b=='b')//wbw
                     {
                         sub(a+1, 1);
                     }
                     else if(s[a]=='b'&& s[a+1]=='b' && s[a+2]=='w' && b=='w')//bbw
                     {
                         add(a+1, 1);
                     }
                  }

              }
              else //在中间，至少左右都有
              {
                  if(a<len-1 &&a>0 && s[a-1]=='w' && s[a]=='w' && s[a+1]=='w'&& b=='b')//www
                  {
                     add(a, 1);//错写成add(a+1,1);
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='w' &&s[a+1]=='b' && b=='b')//wwb
                  {
                     if(s[a+2] == 'w'&& a<len-2)
                     {
                         sub(a+1, 1);
                     }
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='b' &&s[a+1]=='w' && b=='w')//wbw
                  {
                     sub(a, 1); //错写成sub(a+1,1);
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='w' &&s[a+1]=='w' && b=='b')//bww
                  {
                     if(s[a-2] == 'w'&& a>1)
                     {
                         sub(a-1, 1);
                     }
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='b' &&s[a+1]=='b' && b=='w')//bbb
                  {
                     if(s[a+2] == 'w'&& a<len-2)
                     {
                         add(a+1, 1);
                     }
                     if(s[a-2] == 'w'&& a>1)
                     {
                         add(a-1, 1);
                     }
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='b' &&s[a+1]=='w' && b=='w')//bbw
                  {
                     if(s[a-2] == 'w'&& a>1)
                     {
                         add(a-1, 1);
                     }
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='w' &&s[a+1]=='b' && b=='b')//bwb
                  {
                     if(s[a+2] == 'w'&& a<len-2)
                     {
                         sub(a+1, 1);
                     }
                     if(s[a-2] == 'w'&& a>1)
                     {
                         sub(a-1, 1);
                     }
                  }
                  else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='b' &&s[a+1]=='b' && b=='w')//wbb
                  {
                     if(s[a+2] == 'w'&& a<len-2)
                     {
                         add(a+1, 1);
                     }
                  }
              }
              s[a] = b; //一定要记得更新
           }
       }
    }
    return 0;
}

2011-09-19 17:48 发表于百度空间，今搬至CU。