Codeforces Round #316 (Div. 二)ProblemC

Codeforces Round #316 (Div. 2)ProblemC
题目大意：有一个长度为n的字符串，和m次询问$(1 ≤ n, m ≤ 300 000)$，字符串由小写字母和’.’组成，每次询问给一个整数x和字符c$(1 ≤ xi ≤ n, ci是字母或者'.')$，用c这个字符去替换原字符串x的位置的字符，然后统计连续的两个’.’的个数。关于统计’.’的个数：例如，“h…i..”，前3个连续点，有2组连续的两个’.’，后连续的两个点有1组，所以答案是3。所以就是统计字符串里连续两个’.’的个数。

假设先已经统计连续两个’.’的个数为cnt。每次询问将分几种情况讨论：

1.若st[x]字符跟c字符的类型相同，即同为’.’或者同为字母，不论怎么替换总个数cnt是不会改变的
2.若st[x]是字母，c是’.’，增加了’.’的个数，则字符串中有可能会增加连续两个’.’的个数，至于增加多少个呢？若x前一个字符st[x - 1]是个’.’，则会增加1组连续两个’.’，同理st[x + 1]是’.’也会增加一组，其他情况则cnt不变。
3.若st[x]是’.’，c是字母，则字符串中有可能会减少连续两个’.’的个数，同2，只是会减少而已

所以，经过以上分析，可在$O(max(n, m))$时间复杂度内求得答案。

代码如下，仅供参考：

/*************************************************************************
    > File Name: c.cpp
    > Author: Royecode
    > Email: Royecode@163.com 
    > Created Time: 2015年08月14日 星期五 00时20分16秒
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    char st[n + 7];
    scanf("%s", st + 1);
    int cnt = 0;
    for(int i = 1; i <= n; ++i)//求得连续的'.'的个数
        if(st[i] == '.' && st[i + 1] == '.') cnt++;
    while(m--)
    {
        int p;
        char ch[2];
        scanf("%d%s", &p, ch);
        if(ch[0] == '.' && st[p] >= 'a' && st[p] <= 'z')//增加
        {
            if(st[p - 1] == '.') cnt++;
            if(st[p + 1] == '.') cnt++;
        }
        else if(ch[0] >= 'a' && ch[0] <= 'z' && st[p] == '.')//减少
        {
            if(st[p - 1] == '.') cnt--;
            if(st[p + 1] == '.') cnt--;
        }
        printf("%d\n", cnt);
        st[p] = ch[0];
    }
    return 0;
}