链接&＃xff1a;
http://acm.hust.edu.cn/vjudge/contest/view.action?cid&＃61;87813#problem/J
Description
Daniel has a string s, consisting of lowercase English letters and period signs (characters &＃39;.&＃39;). Let&＃39;s define the operation of replacement as the following sequence of steps: find a substring ".." (two consecutive periods) in string s, of all occurrences of the substring let&＃39;s choose the first one, and replace this substring with string ".". In other words, during the replacement operation, the first two consecutive periods are replaced by one. If string s contains no two consecutive periods, then nothing happens.
Let&＃39;s define f(s) as the minimum number of operations of replacement to perform, so that the string does not have any two consecutive periods left.
You need to process m queries, the i-th results in that the character at position xi (1 ≤ xi ≤ n) of string s is assigned value ci. After each operation you have to calculate and output the value of f(s).
Help Daniel to process all queries.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) the length of the string and the number of queries.
The second line contains string s, consisting of n lowercase English letters and period signs.
The following m lines contain the descriptions of queries. The i-th line contains integer xi and ci (1 ≤ xi ≤ n, ci — a lowercas English letter or a period sign), describing the query of assigning symbol ci to position xi.
Output
Print m numbers, one per line, the i-th of these numbers must be equal to the value of f(s) after performing the i-th assignment.
Sample Input
10 3
.b..bz....
1 h
3 c
9 f
4
3
1
4 4
.cc.
2 .
3 .
2 a
1 a
1
3
1
1
Hint
Note to the first sample test (replaced periods are enclosed in square brackets).
The original string is ".b..bz....".
- after the first query f(hb..bz....) &＃61; 4 ("hb[..]bz...." → "hb.bz[..].." → "hb.bz[..]." → "hb.bz[..]" → "hb.bz.")
- after the second query f(hbс.bz....) &＃61; 3 ("hbс.bz[..].." → "hbс.bz[..]." → "hbс.bz[..]" → "hbс.bz.")
- after the third query f(hbс.bz..f.) &＃61; 1 ("hbс.bz[..]f." → "hbс.bz.f.")
Note to the second sample test.
The original string is ".cc.".
- after the first query: f(..c.) &＃61; 1 ("[..]c." → ".c.")
- after the second query: f(....) &＃61; 3 ("[..].." → "[..]." → "[..]" → ".")
- after the third query: f(.a..) &＃61; 1 (".a[..]" → ".a.")
- after the fourth query: f(aa..) &＃61; 1 ("aa[..]" → "aa.")
找到了规律很水的AC了&＃xff0c;但看了题解后知道原来这是个线段树&＃xff0c; 两个代码都粘一下
水的代码&＃xff1a;
#include
#include<string.h>#define N 301100char s[N];int main()
{int n, m, sum, z;while(scanf("%d%d", &n, &m)!&＃61;EOF){char ch;int k, i;scanf("%s", s);sum&＃61;0;for(i&＃61;0; i
}
线段树&＃xff1a;
/*************************************************************************> File Name: C.cpp> Author: ALex> Mail: zchao1995&＃64;gmail.com > Created Time: 2015年08月14日 星期五 01时09分43秒************************************************************************/#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
京公网安备 11010802041100号