1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5  6 const int N = 50007; 7  8 int tree[N], n; 9 char str[N];10 11 int lowbit(int x)12 {13     return (x & -x);14 }15 16 void update(int pos, int val)17 {18     while (pos <= n)19     {20         tree[pos] += val;21         pos += lowbit(pos);22     }23 }24 25 int find(int pos)26 {27     int sum = 0;28     while (pos > 0)29     {30         sum += tree[pos];31         pos -= lowbit(pos);32     }33     return sum;34 }35 36 int main()37 {38     int t, m, cas;39     while (scanf("%d", &t) != EOF)40     {41         cas = 0;42         while (t--)43         {44             memset(tree, 0, sizeof(tree));45             printf("Case %d:\n", ++cas);46             scanf("%d%d", &n, &m);47             getchar();48             scanf("%s", str + 1);49             for (int i = 3; i <= n; i++)50             {51                 if (str[i] == ‘w‘ && str[i-1] == ‘b‘ && str[i-2] == ‘w‘)52                     update(i, 1);53             }54             int op;55             for (int i = 0; i < m; i++)56             {57                 scanf("%d", &op);58                 if (op == 0)59                 {60                     int a, b;61                     scanf("%d%d", &a, &b);62                     a++, b++;63                     if (b - a < 2)64                         printf("0\n");65                     else66                         printf("%d\n", find(b) - find(a + 1));67                 }68                 else69                 {70                     int a;71                     char c;72                     scanf("%d %c", &a, &c);73                     a++;74                     if (str[a] == c)75                         continue;76                     if (a >= 3 && str[a] == ‘w‘ && str[a-1] == ‘b‘ && str[a-2] == ‘w‘)77                         update(a, -1);78                     if (a > 1 && a <= n - 1 && str[a-1] == ‘w‘ && str[a] == ‘b‘ && str[a+1] == ‘w‘)79                         update(a + 1, -1);80                     if (a <= n - 2 && str[a] == ‘w‘ && str[a+1] == ‘b‘ && str[a+2] == ‘w‘)81                         update(a + 2, -1);82                     str[a] = c;83                     if (a >= 3 && str[a] == ‘w‘ && str[a-1] == ‘b‘ && str[a-2] == ‘w‘)84                         update(a, 1);85                     if (a > 1 && a <= n - 1 && str[a-1] == ‘w‘ && str[a] == ‘b‘ && str[a+1] == ‘w‘)86                         update(a + 1, 1);87                     if (a <= n - 2 && str[a] == ‘w‘ && str[a+1] == ‘b‘ && str[a+2] == ‘w‘)88                         update(a + 2, 1);89                 }90             }91         }92     }93 }