CF Round 984 C. Anya and 1100（模拟）

传送门https://codeforces.com/contest/2036/problem/C

解题思路

先扫一遍字符串，判断有几个 1100 子串。

然后，对于每一次操作，可以算出对答案的影响，减去更改会减少的子串，再加上更改后会增加的子串。

代码

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

char s[200001];
int q,t;
int n;
int cnt;

int p;
char ch;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>t;
	while(t--)
	{
	cin>>s;
	n=strlen(s);
	cin>>q;
	cnt=0;
	for(int i=0;i+3<n;i++)
	{
		if(s[i]=='1'&&s[i+1]=='1'&&s[i+2]=='0'&&s[i+3]=='0')
		{
			cnt++;
		}
	}
	
	while(q--)
	{
		cin>>p>>ch;
		
		if(s[p-1]==ch)
		{
			if(cnt)
				cout<<"YES\n";
			else
				cout<<"NO\n";
		}
		else{
			if(p-1>=0&&p+2<n)
			{
				if(s[p-1]=='1'&&s[p]=='1'&&s[p+1]=='0'&&s[p+2]=='0')
					cnt--;
			}
			if(0<=p-2&&p+1<n)
			{
				if(s[p-2]=='1'&&s[p-1]=='1'&&s[p]=='0'&&s[p+1]=='0')
					cnt--;
			}
			if(0<=p-3&&p<n)
			{
				if(s[p-3]=='1'&&s[p-2]=='1'&&s[p-1]=='0'&&s[p]=='0')
					cnt--;
			}
			if(0<=p-4&&p-1<n)
			{
				if(s[p-4]=='1'&&s[p-3]=='1'&&s[p-2]=='0'&&s[p-1]=='0')
					cnt--;
			}
			s[p-1]=ch;
			if(p-1>=0&&p+2<n)
			{
				if(s[p-1]=='1'&&s[p]=='1'&&s[p+1]=='0'&&s[p+2]=='0')
					cnt++;
			}
			if(0<=p-2&&p+1<n)
			{
				if(s[p-2]=='1'&&s[p-1]=='1'&&s[p]=='0'&&s[p+1]=='0')
					cnt++;
			}
			if(0<=p-3&&p<n)
			{
				if(s[p-3]=='1'&&s[p-2]=='1'&&s[p-1]=='0'&&s[p]=='0')
					cnt++;
			}
			if(0<=p-4&&p-1<n)
			{
				if(s[p-4]=='1'&&s[p-3]=='1'&&s[p-2]=='0'&&s[p-1]=='0')
					cnt++;
			}
			if(cnt)
				cout<<"YES\n";
			else
				cout<<"NO\n";
		}
	}
	}
	return 0;
}