E
link
这个题目中所说的好的其实就是像\(010101\)这样一个\(0\)，一个\(1\)的字符串。
那么不好的就是两个\(0\)或两个\(1\)在一起，所以判断一个区间好不好只需要判断一个区间内有没有两个\(0\)或两个\(1\)在一起，那么我们可以把两个\(0\)或两个\(1\)在一起的位置存下来。
先考虑查询操作。
我们只需要判断\(l\)到\(r\)之间有没有两个\(0\)或两个\(1\)在一起，如果所存的位置是升序的，可以直接用二分来做，于是想到了\(set\)。
再考虑修改。
其实修改就是开头和结尾会改变，那么如果原来的开头是好的（\(set\)里没有），那么会变成坏的，反之亦然。结尾也一样。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
char s[500005];
set<int> st;
signed main(){
cin >> n >> q;
cin >> s+1;
for(int i = 2;i <= n;++ i)
if(s[i] == s[i-1]) st.insert(i);
while(q--){
int op,l,r;
cin >> op >> l >> r;
if(op == 1){
if(l > 1){
if(st.count(l)){
st.erase(l);
}
else st.insert(l);
}
if(r < n){
if(st.count(r+1)){
st.erase(r+1);
}
else st.insert(r+1);
}
}
if(op == 2){
auto it = st.upper_bound(l);
if(it == st.end()||*it > r){
cout << "Yes\n";
}
else cout << "No\n";
}
}
return 0;
}