Codeforces Round #316 (Div. 2) C Replacement 扫描法

先扫描一遍得到每个位置向后连续的'.'的长度，包含自身，然后在扫一遍求出初始的合并次数。

对于询问，只要对应位置判断一下是不是'.'，以及周围的情况。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+5;
char s[maxn];
int post[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m; scanf("%d%d",&n,&m); //getchar();
    scanf("%s",s);
    post[n-1] = s[n-1] == '.';
    for(int i = n-2; i >= 0; i--){
        if(s[i] == '.'){
            post[i] = post[i+1]+1;
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '.'){
            cnt += post[i]-1;
            i += post[i];
        }
    }
    char ch[10];
    while(m--){
        int i;
        scanf("%d%s",&i,ch); i--;
        if(ch[0] == '.'){
            if(s[i] == '.'){
                printf("%d
",cnt);
            }else {
                bool f1 = i>0 && s[i-1] == '.';
                bool f2 = i+1<n && s[i+1] == '.';
                cnt += f1+f2;
                printf("%d
",cnt);
            }
        }else {
            if(s[i] == '.'){
                bool f1 = i>0 && s[i-1] == '.';
                bool f2 = i+1<n && s[i+1] == '.';
                cnt -= f1+f2;
                printf("%d
",cnt);
            }else {
               printf("%d
",cnt);
            }
        }
        s[i] = ch[0];
    }
    return 0;
}