五場(chǎng)的網(wǎng)絡(luò)賽的題目出現(xiàn)了大量的線段樹的題目，每次都只能坐在那里干瞪眼。。

看來(lái)需要好好的啃啃線段樹了。。

?

#include<iostream>
#include<string>?
#define maxn 50010?
#define lson l , m , rt << 1?
#define rson m + 1 , r , rt << 1 | 1?
using namespace std;?
int sum[maxn*4];?
char str[maxn];?
int a[maxn];?
void PushUP(int rt)
?{?
??? sum[rt] = sum[rt<<1] + sum[rt<<1|1];?
}?
void build(int l,int r,int rt)
?{?
??? if (l == r) {?
??????? sum[rt]=a[l];?
??????? return ;?
??? }?
??? int m = (l + r) >> 1;?
??? build(lson);?
??? build(rson);?
??? PushUP(rt);?
}?

void update(int p,int add,int l,int r,int rt)
?{?
??? if (l == r)
?{?
??????? sum[rt] = add;?
??????? return ;?
??? }?
??? int m = (l + r) >> 1;?
??? if (p <= m) update(p , add , lson);?
??? else update(p , add , 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 (R > m) ret += query(L , R , rson);?
??? return ret;?
}?
int main()?
{?
??? int cas,T=0,n,m,r,l,c;?
??? char st;?
??? scanf("%d",&cas);?
??? while(cas--)?
??? {?
??????? scanf("%d %d",&n,&m);?
??????? scanf("%s",str);?
??????? memset(a,0,sizeof(a));?
??????? printf("Case %d:\n",++T);?
??????? for(int i=2;i<n;i++)//標(biāo)記以該下標(biāo)結(jié)尾的長(zhǎng)度為3的子串是否符合要求?
??????? {?
??????????? if(str[i]!='w')?
??????????????? a[i]=0;?
??????????? else if(str[i-1]=='b'&&str[i-2]=='w')?
??????????????? a[i]=1;?
??????? }?
??????? build(0,n,1);?
??????? while(m--)?
??????? {?
??????????? scanf("%d",&c);?
??????????? if(c==0)?
??????????? {?
??????????????? scanf("%d %d",&l,&r);?
????l+=2;?
??????????????? if(l>r) printf("0\n");?
??????????????? else?
?????printf("%d\n",query(l,r,0,n,1));?
??????????? }?
??????????? else?
??????????? {?
??????????????? scanf("%d %c",&l,&st);?
??????????????? if(str[l]==st)//若要就該的字符跟原先相同，則不用修改了?
??????????????????? continue;?
??????????????? str[l]=st;?
??????????????? if(l>=2&&str[l-2]=='w'&&str[l-1]=='b'&&str[l]=='w')?
??????????????? {?
??????????????????? if(a[l]==0)//若改之前是不符合要求的串，則更新?
??????????????????????? update(l,1,0,n,1);?
??????????????????? a[l]=1;?
??????????????? }?
??????????????? else if(l>=2&&a[l]==1)//若改之前是符合要求的串，則更新?
??????????????? {?
??????????????????? update(l,0,0,n,1);?
??????????????????? a[l]=0;?
??????????????? }?
??????????????? if(l>=1&&str[l]=='b'&&str[l-1]=='w'&&str[l+1]=='w')?
??????????????? {?
??????????????????? if(a[l+1]==0)?
??????????????????????? update(l+1,1,0,n,1);?
??????????????????? a[l+1]=1;?
??????????????? }?
??????????????? else if(l<n-1&&l>=1&&a[l+1]==1) a[l+1]=0,update(l+1,0,0,n,1);?
??????????????? if(str[l]=='w'&&str[l+1]=='b'&&str[l+2]=='w')?
??????????????? {?
??????????????????? if(a[l+2]==0)?
??????????????????????? update(l+2,1,0,n,1);?
??????????????????? a[l+2]=1;?
??????????????? }?
??????????????? else
?????if(l<n-2&&a[l+2]==1)
??????a[l+2]=0,update(l+2,0,0,n,1);?
??????????? }?
??????? }?
??? }?
??? return 0;?
}

轉(zhuǎn)載于:https://www.cnblogs.com/Mu-Tou/archive/2011/09/21/2184445.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4046 Panda 线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。