hdu 4046 Panda 解题报告
题目大意，输出入一行字符串，用两种字符b,w； 如果连续三个字符是wbw，那么就代表我爱你，问一行字符串中能有多少个我爱你！ 注：wbwbw视为两个！ 然后又询问和修改！ 数据规模：字符串长度n=5W，询问1W； 典型的树状数组或者用线段树就可以做！ 注意一个字符的修改会影响到他自身或者右边相邻的两位，用树状数组时，getsum(r)-get(l+1) 为什么呢，因为一个这段被截取之后，开头的两个字符与前面被截取的字符否成三分合法字符的话不应该计数了……
这个小题当时思路很清晰，但是有出了两个小bug，一个是修改命令忘了修改数组中的对应项了，还有一个就是键盘不好使，在if中的判断语句双等号写成单等号复制语句了，该死的codeblock又不报错！ 改了一上午，各种调试！ 好怀念java啊！
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 50010
using namespace std;
int n,m;
int test;
char ch[MAXN];
int a[MAXN];
int c[MAXN];
int lowbit(int x)
{
return x&(-x);
}
int getsum(int x)
{
int ret=0;
while(x>0)
{
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int d)
{
///给数组c添加d
while(x<n+5)
{
c[x]+=d;
x+=lowbit(x);
}
}
int main()
{
// cout<<lowbit(2)<<endl;
// cout<<lowbit(6)<<endl;;
cin>>test;
int cas=0;
while(cas++<test)
{
char ch0;
scanf("%d %d",&n,&m);gets(ch);
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[0]=-1;
gets(ch);
if(ch[0]=='w')a[1]=1;
for(int i=2; i<=n; ++i)
{
if(ch[i-1]=='w')
{
/// cout<<"ok========="<<endl;
a[i]=1;
if(a[i-1]==0&&a[i-2]==1)
{
add(i,1);
}
}
}
int cmd,l,r;
cout<<"Case "<<cas<<":"<<endl;
for(int i=0; i<m; ++i)
{
scanf("%d",&cmd);
if(cmd)
{
scanf("%d %c",&l,&ch0);
l++;
if(ch0=='w'&&a[l]==0)
{///cout<<"okokoko===okokok===："<<a[3]<<a[4]<<a[5]<<endl;
if(l>=2&&a[l-1]==0&&a[l-2]==1) add(l,1);
if(l<=n-2&&a[l+1]==0&&a[l+2]==1)add(l+2,1);
if(a[l-1]==1&&a[l+1]==1)add(l+1,-1);
a[l]=1;
}
else if(ch0=='b'&&a[l]==1)
{///cout<<"okokoko===okokok===2222!!!："<<a[3]<<a[4]<<a[5]<<endl;
if(l>=2&&a[l-1]==0&&a[l-2]==1) add(l,-1);
if(l<=n-2&&a[l+1]==0&&a[l+2]==1)add(l+2,-1);
if(a[l+1]==1&&a[l-1]==1)add(l+1,1);///!!!
a[l]=0;///cout<<"okokoko===okokok===2222!!!："<<a[3]<<a[4]<<a[5]<<endl;
}///for(int j=1; j<=n; ++j)cout<<"====="<<a[j]<<endl;
}
else
{
scanf("%d %d",&l,&r);
l++;r++;
if(r<=l+1)cout<<0<<endl;
else printf("%d\n",getsum(r)-getsum(l+1)); ///for(int j=1; j<=n; ++j)cout<<"=========="<<a[j]<<endl;
}
cmd=0;
}
}
return 0;
}