本文主要是介绍The 36th ACM/ICPC Asia Regional Beijing Sitehttp://acm.hdu.edu.cn/showproblem.php?pid=4046，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比较难的线段树题，，，
#include<iostream>
#include<cstdio>
#include<string.h>
#define N 50005
using namespace std;
typedef struct NODE
{int l;int r;int key;
}Node;
Node node[N<<2];
char str[N];
void build(int t,int l,int r)
{node[t].l=l;node[t].r=r;if(r==l){if(l<=2) {node[t].key=0;return;}if(str[l]=='w'&&str[l-1]=='b'&&str[l-2]=='w') node[t].key=1;else node[t].key=0;return;}int mid=(l+r)>>1;build(t<<1,l,mid);build(t<<1|1,mid+1,r);node[t].key=node[t<<1].key+node[t<<1|1].key;
}
void update(int t,int l,int r,char ch)
{if(node[t].l==l&&node[t].r==r){ str[l]=ch;if(l<=2) return;if(str[l]=='w'&&str[l-1]=='b'&&str[l-2]=='w') node[t].key=1;else node[t].key=0;return ;}if(l>=node[t<<1|1].l) update(t<<1|1,l,r,ch);else if(r<=node[t<<1].r) update(t<<1,l,r,ch);else{ update(t<<1,l,node[t<<1].r,ch);update(t<<1|1,node[t<<1|1].l,r,ch);}node[t].key=node[t<<1].key+node[t<<1|1].key;
}
int Quary(int t,int l,int r)
{if(node[t].l==l&&node[t].r==r) return node[t].key;if(l>=node[t<<1|1].l) return Quary(t<<1|1,l,r);else if(r<=node[t<<1].r) return Quary(t<<1,l,r);else return Quary(t<<1,l,node[t<<1].r)+Quary(t<<1|1,node[t<<1|1].l,r);
}
int main()
{int T;scanf("%d",&T);for(int k=1;k<=T;++k){printf("Case %d:\n",k);int n,m;scanf("%d%d",&n,&m);str[0]=0;scanf("%s",str+1);build(1,1,n);for(int i=0;i!=m;++i){int x;scanf("%d",&x);if(x==0) { int y,z;scanf("%d%d",&y,&z);if(z-y+1<3) printf("0\n");else printf("%d\n",Quary(1,y+3,z+1));}else{int y;char z;scanf("%d",&y);getchar();scanf("%c",&z);update(1,y+1,y+1,z);if(y+1<n) update(1,y+2,y+2,str[y+2]);if(y+2<n) update(1,y+3,y+3,str[y+3]);}}}return 0;
}这篇关于The 36th ACM/ICPC Asia Regional Beijing Sitehttp://acm.hdu.edu.cn/showproblem.php?pid=4046的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
