HDU 4046 Panda：線段樹維護「wbw」子串計數與單點修改

問題描述

給定一個只包含 'w'（白）和 'b'（黑）的字符串，支持兩種操作：

1. 查詢：區間 [L, R] 內有多少個連續子串 "wbw"。
2. 修改：將第 k 個字符改為 'w' 或 'b'。

字符串長度 n ≤ 50000，查詢次數 m ≤ 10000。

核心觀察：「wbw」的局部性

"wbw" 長度為 3，且只與相鄰三個字符有關。若在位置 i（1-based）出現 "wbw"，必滿足 s[i-1]=='w' && s[i]=='b' && s[i+1]=='w'。因此，我們可以預處理一個標記數組 a[i]：

a[i] = 1, 若 s[i-1..i+1] == "wbw"
a[i] = 0, 否則

則區間 [L, R] 內 "wbw" 的個數 = sum(a[L+1 .. R-1])（注意邊界：L+1 ≤ R-1 才可能有完整 "wbw"）。

線段樹維護區間和

由於有單點修改、區間求和，線段樹是完美選擇：

• 構建：O(n)
• 單點更新：O(log n)
• 區間查詢：O(log n)

修改操作的影響範圍

修改位置 k 只會影響以 k-2, k-1, k 為中心的三個潛在 "wbw"（即 a[k-1], a[k], a[k+1]）。具體邏輯：

// 修改位置 x (0-based) 為字符 ch
if (str[x] == ch) return;  // 無實際變化
str[x] = ch;

// 檢查三個受影響的中心位置：x-1, x, x+1 (對應 a[x], a[x+1], a[x+2] 1-based)
for (int center = x - 1; center <= x + 1; ++center) {
    if (center < 1 || center >= n - 1) continue;  // 邊界檢查
    bool now = (str[center-1]=='w' && str[center]=='b' && str[center+1]=='w');
    if (now && a[center]==0) { update(center, 1); a[center]=1; }
    else if (!now && a[center]==1) { update(center, 0); a[center]=0; }
}

完整代碼框架

#include 
using namespace std;
const int MAXN = 50010;

struct Node { int l, r, sum; } t[MAXN<<2];
int a[MAXN];  // 標記數組
char str[MAXN];
int n, m;

void build(int l, int r, int idx) { /* 標準線段樹構建 */ }
void update(int pos, int val, int idx) { /* 單點更新 */ }
int query(int L, int R, int idx) { /* 區間求和 */ }

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        scanf("%d%d", &n, &m);
        scanf("%s", str);
        memset(a, 0, sizeof(a));
        // 預處理 a[]
        for (int i = 1; i < n-1; ++i)
            if (str[i-1]=='w' && str[i]=='b' && str[i+1]=='w') a[i+1] = 1; // 1-based
        build(1, n, 1);
        
        printf("Case %d:\n", cas);
        while (m--) {
            int type; scanf("%d", &type);
            if (type == 0) {
                int L, R; scanf("%d%d", &L, &R);
                if (R - L < 2) puts("0");
                else printf("%d\n", query(L+1, R-1, 1));
            } else {
                int k; char ch; scanf("%d %c", &k, &ch);
                // 執行上述修改邏輯
            }
        }
    }
    return 0;
}

複雜度分析

• 預處理：O(n)
• 每次查詢/修改：O(log n)
• 總時間：O((n + m) log n)，完全滿足限制。

總結

本題關鍵在於將子串匹配問題轉化為區間和問題，利用「wbw」長度固定且局部性強的特點，構造標記數組 + 線段樹，優雅解決動態查詢與修改。這是「線段樹維护區間屬性」的經典套路。