Codeforces 316C Replacement：連續點號替換的 O(1) 查詢維護

題目大意

• 字符串 s（長度 n ≤ 3e5），包含小寫字母和 '.'。
• 操作：將 s[x] 改為字符 c，每次修改後輸出 f(s) = 消除所有連續 ".." 所需最小替換次數（每次替換將最左邊的 ".." 變為 "."）。
• m ≤ 3e5 次查詢。

規律洞察

f(s) 等於所有最大連續點段長度 len 的 len-1 之和。
因為長度為 L 的點段需 L-1 次替換才能變為單點。

O(1) 單點更新

維護全局答案 `ans`。修改位置 `pos` 時，僅影響 `pos` 及其左右相鄰的點段邊界。
設 `old = s[pos]`，`nw = c`。

• 若 `old == '.' && nw != '.'`：移除一個點。
   檢查左鄰是否為點 → `ans--`。
   檢查右鄰是否為點 → `ans--`。
   （原本這兩個邊界各貢獻 1 次替換，現消失）
• 若 `old != '.' && nw == '.'`：新增一個點。
   檢查左鄰是否為點 → `ans++`。
   檢查右鄰是否為點 → `ans++`。
• 其他情況 `ans` 不變。

完整代碼

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    string s; cin >> s;
    long long ans = 0;
    for (int i = 0; i < n; ) {
        if (s[i] == '.') {
            int j = i;
            while (j < n && s[j] == '.') ++j;
            ans += j - i - 1;
            i = j;
        } else ++i;
    }
    while (m--) {
        int pos; char c; cin >> pos >> c; --pos;
        if (s[pos] != c) {
            if (s[pos] == '.') { // 移除點
                if (pos > 0 && s[pos-1] == '.') --ans;
                if (pos+1 < n && s[pos+1] == '.') --ans;
            } else if (c == '.') { // 新增點
                if (pos > 0 && s[pos-1] == '.') ++ans;
                if (pos+1 < n && s[pos+1] == '.') ++ans;
            }
            s[pos] = c;
        }
        cout << ans << "\n";
    }
    return 0;
}

線段樹備選方案

維護區間：
`sum` = 區間內替換次數，`l` = 左端是否為點，`r` = 右端是否為點。
合併：`sum = L.sum + R.sum + (L.r && R.l)`。
單點更新、查詢整條鏈 `sum`，複雜度 O(log n)，常數較大但通用。

複雜度

• 規律法：預處理 O(n)，每查詢 O(1)，總 O(n+m)。
• 線段樹：O((n+m) log n)。