【HDU】4046 Panda

  1 #include<cstdio>
  2 #define MAX(a,b) ((a)>(b)?(a):(b))
  3 #define MAXN 50010
  4 char s[MAXN];
  5 int tree[MAXN<<2];
  6 inline void PushUp(int rt)
  7 {
  8     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
  9 }
 10 inline bool OK(int i)
 11 {
 12     return s[i]=='w'&&s[i+1]=='b'&&s[i+2]=='w';
 13 }
 14 void Build(int L,int R,int rt)
 15 {
 16     if(L==R)
 17         tree[rt]=OK(L)?1:0;
 18     else
 19     {
 20         int mid=(L+R)>>1;
 21         Build(L,mid,rt<<1);
 22         Build(mid+1,R,rt<<1|1);
 23         PushUp(rt);
 24     }
 25 }
 26 void Update(int x,int L,int R,int rt)
 27 {
 28     if(L==R)
 29         tree[rt]=OK(L)?1:0;
 30     else
 31     {
 32         int mid=(L+R)>>1;
 33         if(mid>=x)
 34             Update(x,L,mid,rt<<1);
 35         else
 36             Update(x,mid+1,R,rt<<1|1);
 37         PushUp(rt);
 38     }
 39 }
 40 int Query(int x,int y,int L,int R,int rt)
 41 {
 42     if(x<=L&&R<=y)
 43         return tree[rt];
 44     int mid=(L+R)>>1,ans=0;
 45     if(mid>=x)
 46         ans+=Query(x,y,L,mid,rt<<1);
 47     if(y>mid)
 48         ans+=Query(x,y,mid+1,R,rt<<1|1);
 49     return ans;
 50 }
 51 int main()
 52 {
 53     char ch;
 54     int x,y,type,c,i,n,q,ca=1;
 55     scanf("%d",&c);
 56     while(c--)
 57     {
 58         scanf("%d%d %s",&n,&q,s);
 59         n-=3;
 60         printf("Case %d:\n",ca++);
 61         if(n<0)
 62         {
 63             while(q--)
 64             {
 65                 scanf("%d%d",&type,&x);
 66                 if(type)
 67                     scanf(" %c",&ch);
 68                 else
 69                 {
 70                     scanf("%d",&y);
 71                     puts("0");
 72                 }
 73             }
 74         }
 75         else
 76         {
 77             Build(0,n,1);
 78             while(q--)
 79             {
 80                 scanf("%d%d",&type,&x);
 81                 if(type)
 82                 {
 83                     scanf(" %c",&ch);
 84                     if(s[x]!=ch)
 85                     {
 86                         s[x]=ch;
 87                         for(i=MAX(0,x-2);i<=x;i++)
 88                             Update(i,0,n,1);
 89                     }
 90                 }
 91                 else
 92                 {
 93                     scanf("%d",&y);
 94                     if(x>y-2)
 95                         puts("0");
 96                     else
 97                         printf("%d\n",Query(x,y-2,0,n,1));
 98                 }
 99             }
100         }
101     }
102     return 0;
103 }
新博客：www.zhixiangli.com