思路是維護每個字母開頭，長度為3的串是不是wbw……
這樣相當于將長度為N的字符串變成長度為N－2的序列，然后一系列修改就是將序列中1變0，0變1，查詢就是求一段的和
BIT，大家都懂的……
1 #include <cstdio>
2 #include <cstring>
3
4 int n,m;
5 char str[50010];
6 int arr[50010];
7
8 inline int lowbit(int x) {return x & -x;}
9
10 void update(int x,int delta) {
11 for (int i = x; i <= n; i += lowbit(i)) {
12 arr[i] += delta;
13 }
14 }
15
16 int sum(int x) {
17 int ret = 0;
18 while (x) {ret += arr[x]; x -= lowbit(x);}
19 return ret;
20 }
21
22 int sum(int l,int r) {
23 if (l > r) return 0;
24 if (l == 0) return sum(r);
25 return sum(r) - sum(l - 1);
26 }
27
28 int main() {
29 int nn; scanf("%d",&nn);
30 for (int ii = 1; ii <= nn; ii++) {
31 scanf("%d%d",&n,&m);
32 memset(str,0,sizeof(str));
33 memset(arr,0,sizeof(arr));
34 scanf("%s",str + 1);
35 for (int i = 1; i + 2 <= n; i++) {
36 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
37 update(i,1);
38 }
39 }
40 printf("Case %d:\n",ii);
41 while (m--) {
42 int ctrl; scanf("%d",&ctrl);
43 if (ctrl == 0) {
44 int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum(l + 1,r - 1));
45 } else {
46 int pos; char buf[10]; scanf("%d",&pos); scanf("%s",buf); pos ++;
47 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
48 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
49 update(i,-1);
50 }
51 }
52 str[pos] = buf[0];
53 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
54 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
55 update(i,1);
56 }
57 }
58 }
59 }
60 }
61 return 0;
62 }