atcoder-ABC372-C
codeforces-984div3-C
这里的字串是指连续字串
考虑暴力，对长度为n的母串进行q次操作时间复杂度o(q*n)，1e5级别数据会TLE,考虑优化：
set存储指定字串首字母的下标，修改的字符可能是指定字串的第一个，第二个，...,最后一个字符，考虑修改对这些连续子串的影响，对这些字串进行暴力枚举进行如下更新操作，如果合法则insert，否则erase。答案即为set的大小。
因为字串往往很短，所以时间复杂度可忽略，总时间复杂度o(q)。
ac代码仅供参考：
void solve()
{
int n,q;
cin>>n>>q;
string s;
cin>>s;
set<int>st;
for(int i=0;i+2<s.size();i++){
if(s.substr(i,3)=="ABC")st.insert(i);
}
while(q--)
{
int x;char c;
cin>>x>>c;
s[x-1]=c;
for(int i=max(0ll,x-3);i<=x-1;i++){
if(s.substr(i,3)=="ABC")st.insert(i);
else st.erase(i);
}
cout<<st.size()<<endl;
}
}
void solve()
{
string s;
cin>>s;
int n=s.size();
set<int>st;
auto update=[&](int x){
if(x>=0&&x+3<n){
if(s.substr(x,4)=="1100"){
st.insert(x);
}
else{
st.erase(x);
}
}
};
for(int i=0;i+3<n;i++){
update(i);
}
int q;
cin>>q;
while(q--)
{
int x,y;cin>>x>>y;
char c=(char)('0'+y);
x--;
s[x]=c;
for(int i=x-3;i<=x;i++){
update(i);
}
if(st.size())yes
else no
}
}
