HDU4046Panda （线段树 点更新，段查寻）
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>#define N 50000struct node{ int l,r,ans;}tree[4*N];char c[N+5];int n;int isLove(int l,int r,int ll,int rr)//判断在ll,rr段中，l~r是不是一个LOVE{ if(l<ll||r>rr) return 0; if(c[l]=='w'&&c[l+1]=='b'&&c[r]=='w') return 1; return 0;}void build_Tree(int l,int r,int k)//算出段l~r中love的个数{ int m=(l+r)/2; tree[k].l=l; tree[k].r=r; tree[k].ans=0; if(l==r) return ; build_Tree(l,m,k*2);//更新左 build_Tree(m+1,r,k*2+1);//更新右 int ans=0; for(int i=m-1;i<=m;i++)//计算中间没有连的love ans+=isLove(i,i+2,l,r); tree[k].ans=ans+tree[k*2].ans+tree[2*k+1].ans;//l~r段的love个数=左+右+中间}int L,R,love;void chang_tree(int l,int r,int k)//更新每个段{ int m=(l+r)/2; if(l==L&&L==r) return ; if(L<=m) chang_tree(l,m,k*2); if(L>m) chang_tree(m+1,r,k*2+1); int ans=0; for(int i=m-1;i<=m;i++) ans+=isLove(i,i+2,l,r); tree[k].ans=ans+tree[k*2].ans+tree[2*k+1].ans;}void countLove(int l,int r,int k)//计算L~R段love的个数{ int m=(l+r)/2; if(L<=l&&r<=R){ love+=tree[k].ans; return ; } if(R<=m) countLove(l,m,k*2); else if(L>m) countLove(m+1,r,k*2+1); else { countLove(l,m,k*2); countLove(m+1,r,k*2+1); int ans=0; for(int i=m-1;i<=m;i++) if(i>=L&&i+2<=R) ans+=isLove(i,i+2,l,r); love+=ans; }}int main(){ int t,m,x; char ch; scanf("%d",&t); for(int k=1;k<=t;k++) { scanf("%d%d",&n,&m); if(n) scanf("%s",c); if(n) build_Tree(0,n-1,1); printf("Case %d:\n",k); while(m--) { scanf("%d",&x); if(x==0) { scanf("%d%d",&L,&R); love=0; countLove(0,n-1,1); printf("%d\n",love); } else{ scanf("%d %c",&L,&ch); c[L]=ch; chang_tree(0,n-1,1); } } }}