AT_abc341_e

zibenlun · 2024-02-18 15:37:02 · 题解

思路

题目大意就是可以反转一段区间或查询一段区间中有没有连续的字符。根据题意我们可以维护每两个字符之间是否相等。在修改时可以发现如果两个字符都在区间内，那么其关系不变。所以对于每一次修改我们只需要维护两端的字符之间关系的变化。实现过程中可以使用集合储存所有相邻且相同的字符，最后用二分查询即可。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
set<int> ss;
string s;
int n,q;
int vis[5000005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>s;
    s=" "+s;
    for(int i=1;i<n;i++){
        if(s[i]==s[i+1]){
            vis[i]=1;
            ss.insert(i);
        }
    }
    for(int i=1;i<=q;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            if(x-1!=0){
                if(vis[x-1]){
                    vis[x-1]=0;
                    ss.erase(x-1);
                }
                else {
                    vis[x-1]=1;
                    ss.insert(x-1);
                }               
            }
            if(vis[y]){
                vis[y]=0;
                ss.erase(y);
            }
            else {
                vis[y]=1;
                ss.insert(y);
            }
        }
        else {
            int z=*ss.upper_bound(x-1);
            if(z<y&&z>=x){
                cout<<"No\n";
            }
            else {
                cout<<"Yes\n";
            }
        }
    }
    return 0;
}