题解：CF2248D Good Pair Queries

fish_love_cat · 2026-08-05 02:13:32 · 题解

为什么总是被简单题卡一万年然后彻底倒闭？

因为一个 i 对应的 a_i,b_i 是固定的，考虑捆绑起来考虑。我们用 \{\texttt{00,01,10,11}\} 来分别表示对于 i 有 (a_i,b_i)\in\{(0,0),(0,1),(1,0),(1,1)\} 四类情况。

每步操作你需要保证选出来的 i 组成的集合内 a 和 b 的众数相同，然后删除这个集合内所有的 i。

考虑到 \texttt{01,10} 的处理是较为困难的，另外两者可以独立自己解决比较容易，所以先思考这部分。

容易发现我们可以把 \texttt{01} 和 \texttt{10} 两两配对消灭，然后就剩下一种情况了，不妨钦定剩下的是 \texttt{01}。

显然这个时候添加一个 \texttt{11,00} 都可以把 \texttt{01} 一起消灭掉，所以只要这个串的数量不超过另外两个串数量的总和就做完了。

区间查询的话，我们维护四类点数量的前缀和，复杂度线性。

int qzh[4][200005];
inline void solve(){
    int n,q;
    cin>>n>>q;
    string s,t;
    cin>>s>>t;
    s=" "+s;
    t=" "+t;
    for(int i=1;i<=n;i++){
        for(int op=0;op<4;op++)
        qzh[op][i]=qzh[op][i-1];
        int sum=(s[i]-'0')*2+(t[i]-'0');
        qzh[sum][i]++;
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        int a0=qzh[0][r]-qzh[0][l];
        int a1=qzh[1][r]-qzh[1][l];
        int a2=qzh[2][r]-qzh[2][l];
        int a3=qzh[3][r]-qzh[3][l];
        int qaq=max(a1,a2)-min(a1,a2);
        if(qaq<=a0+a3)cout<<"Yes\n";
        else cout<<"No\n";
    }
}
// 话说究竟为什么会写这种东西……

//「嘿。」
// 我把那页撕了。不理会「啊啊──！」地发出悲痛叫声的艾姆妮西亚，我把纸揉成一团丢进垃圾桶。

//「艾姆妮西亚，我跟你说昨天事情经过的真相，请你仔细听好了。」