Daniel has a strings, consisting of lowercase English letters and period signs (characters ‘.’). Let’s define the operation ofreplacementas the following sequence of steps: find a substring ".." (two consecutive periods) in strings, of all occurrences of the substring let’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 stringscontains no two consecutive periods, then nothing happens.
Let’s definef(s)as the minimum number of operations ofreplacementto perform, so that the string does not have any two consecutive periods left.
You need to processmqueries, thei-th results in that the character at positionxi(1≤xi≤n) of stringsis assigned valueci. After each operation you have to calculate and output the value off(s).
Help Daniel to process all queries.
Input
The first line contains two integersnandm(1≤n,m≤300000) the length of the string and the number of queries.
The second line contains strings, consisting ofnlowercase English letters and period signs.
The followingmlines contain the descriptions of queries. Thei-th line contains integerxiandci(1≤xi≤n,ci— a lowercas English letter or a period sign), describing the query of assigning symbolcito positionxi.
Output
Printmnumbers, one per line, thei-th of these numbers must be equal to the value off(s)after performing thei-th assignment.
Sample test(s)
input
10 3.b..bz….1 h3 c9 f
output
431
input
4 4.cc.2 .3 .2 a1 a
output
1311
#include<iostream>#include<cstdio>#include<cstring>#include<string>using namespace std;int main(){int i,n,m,ans;int t;char ch;string ss;while(scanf("%d%d",&n,&m)!=EOF){cin>>ss;ans=0;for(i=1;i<ss.size();i++){if(ss[i-1]=='.' && ss[i]=='.') ans++;}while(m–) {cin>>t>>ch;t–;if(ch=='.') {if(ss[t]=='.') ;else{if(t>0 && ss[t-1]=='.') ans++;if(t<n && ss[t+1]=='.') ans++;}ss[t]=ch;}else {if(ss[t]!='.') ;else{if(t>0 && ss[t-1]=='.') ans–;if(t<n && ss[t+1]=='.') ans–;}ss[t]=ch;}printf("%d\n",ans);}}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
观今宜鉴古，无古不成今。
