題意：
? ? ? 給一個(gè)字符串，兩種操作 0 a b 詢問(wèn)a,b之間有多少個(gè)wbw, 1 a c 就是把第a個(gè)改成c.

思路：

? ? ? 這個(gè)題目我們可以用線段樹(shù)的點(diǎn)更新來(lái)做，一開(kāi)始寫(xiě)了個(gè)好長(zhǎng)好長(zhǎng)的線段樹(shù)，pushup寫(xiě)了很長(zhǎng)，每個(gè)節(jié)點(diǎn)7個(gè)變量，結(jié)果 ?"呵呵"。其實(shí)根本不用那么麻煩，我當(dāng)時(shí)想的麻煩了，每個(gè)節(jié)點(diǎn)只有一個(gè)sum就行了，每個(gè)節(jié)點(diǎn)代表的是以當(dāng)前這段的每個(gè)點(diǎn)為終點(diǎn)的wbw的個(gè)數(shù)，比如節(jié)點(diǎn)4,6那么當(dāng)前的這個(gè)節(jié)點(diǎn)存的就是以4,5,6，為終點(diǎn)的wbw的個(gè)數(shù)（4,6最多三個(gè)），每次更新的時(shí)候改變當(dāng)前的這個(gè)字母可能會(huì)影響三個(gè)權(quán)值改變，所以更新三次，具體看代碼。

#include<stdio.h> #include<string.h>#define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1 int sum[300000]; char num[55000];void Pushup(int t) {sum[t] = sum[t<<1] + sum[t<<1|1]; }void BuidTree(int l ,int r ,int t) {sum[t] = 0;if(l == r){if(l >= 3 && num[l] == 'w' && num[l-1] == 'b' && num[l-2] == 'w')sum[t] = 1;return ;}int mid = (l + r) >> 1;BuidTree(lson);BuidTree(rson);Pushup(t); }void Update(int l ,int r ,int t ,int a) {if(l == r){if(num[l] == 'w' && num[l-1] == 'b' && num[l-2] == 'w')sum[t] = 1;else sum[t] = 0;return;}int mid = (l + r) >> 1;if(a <= mid) Update(lson ,a);else Update(rson ,a);Pushup(t); }int Query(int l ,int r ,int t ,int a ,int b) {if(a <= l && b >= r)return sum[t];int mid = (l + r) >> 1; int Ans = 0;if(a <= mid) Ans = Query(lson ,a ,b);if(b > mid) Ans += Query(rson ,a ,b);return Ans; }int main () {int t ,n ,m ,a ,b ,c ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);scanf("%s" ,num + 1);BuidTree(1 ,n ,1);printf("Case %d:\n" ,cas ++);while(m--){scanf("%d" ,&a);if(!a){scanf("%d %d" ,&b ,&c);b ++ ,c ++;if(c - b < 2) printf("0\n");else printf("%d\n" ,Query(1 ,n ,1 ,b + 2 ,c));}else {char str[5];scanf("%d %s" ,&b ,str);num[++b] = str[0];if(b >= 3) Update(1 ,n ,1 ,b);if(b + 1 >= 3 && b + 1 <= n) Update(1 ,n ,1 ,b + 1);if(b + 2 >= 3 && b + 2 <= n) Update(1 ,n ,1 ,b + 2);}}}return 0; }

總結(jié)

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

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