传送门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";elsecout<<"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";elsecout<<"NO\n";}}}return 0;
}