Description
Input
Output
Sample Input
2 5 2 bwbwb 0 0 4 0 1 3 5 5 wbwbw 0 0 4 0 0 2 0 2 4 1 2 b 0 0 4
Sample Output
Case 1: 1 1 Case 2: 2 1 1 0
解题思路
一开始,如何更新写的特别拙,后来看了LXCC发的代码,精简的多,就是查询时好像必须是整型输入
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 50010;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int sum[maxn << 2], ans[maxn];
char str[maxn];
void PushUp(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
sum[rt] = 0;
if(l == r)
{
sum[rt] = ans[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int p, int c, int l, int r, int rt)
{
if(l == r)
{
sum[rt] = c;
return;
}
int m = (l + r) >> 1;
if(p <= m)
update(p, c, lson);
else
update(p, c, rson);
PushUp(rt);
}
int query(int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R)
return sum[rt];
int m = (l + r) >> 1;
int ret = 0;
if(L <= m)
ret += query(L, R, lson);
if(m < R)
ret += query(L, R, rson);
return ret;
}
int main()
{
int t, n, m, kase = 0;
scanf("%d", &t);
while(t--)
{
printf("Case %d:\n", ++kase);
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
int a, b;
char c[2];
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= n - 2; i++)
{
if(str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w')
ans[i] = 1;
}
build(1, n, 1);
while(m--)
{
scanf("%d", &a);
if(a)
{
scanf("%d%s", &b, c);
str[b + 1] = c[0];
for(int i = 0; i <= 2; i++)
{
int t;
if(b + 1 - i)
{
if(b - i + 3 <= n && str[b + 1 - i] == 'w' && str[b - i + 2] == 'b' && str[b - i + 3] == 'w')
t = 1;
else
t = 0;
if(t != ans[b - i + 1])
{
update(b - i + 1, t, 1, n, 1);
ans[b - i + 1] = t;
}
}
}
}
else
{
scanf("%d%d", &a, &b);
if(b - a >= 2)
printf("%d\n", query(a + 1, b - 1, 1, n, 1));
else
printf("0\n");
}
}
}
return 0;
}