[NOI2025] 三目运算符

· · 题解

题目分析

非常有意思的思维题。

首先我们弱化题目，考虑不用反转怎么做。

我们考虑相邻的 3 个数什么情况下会变化：s_i\ne s_{i-1},s_{i-2}=\texttt{1} 同时成立。显然这种情况只有 \texttt{110},\texttt{101}。

我们考虑目前已经有一个不动的前缀 p 和字符 c。我们只关心 p 的最后 2 个字符，不妨设为 a,b。

如果 abc 构成 \texttt{110}，显然下一时刻 c\gets \texttt{1}，由于 a=\texttt{1},b=\texttt{1}，所以下一时刻无论 b 从哪里转移过来 b 一定也是 \texttt{1}。考虑 c 后面的一个字符 d，\texttt{10}d 中 d 从前面的 c(c=\texttt{0}) 转移过来，即 d=\texttt{0}。这样 abc\to bcd，依次向后。假设一开始 a 的下标是 i 那么会变化 n-i-1 次。

考虑 abc 构成 \texttt{101}，下一次变化会变为 \texttt{100}。不会继续变化。

提示：上面两种情况 ab 不变是基于已经有一个不动的前缀的假设。

接下来考虑前缀变化对 \texttt{110},\texttt{101} 的影响。

显然有 \texttt{110} 应该优先考虑，因为它的贡献更大。前面的一个 \texttt{110} 会覆盖后面一个的贡献，所以取最靠前的。考虑 \texttt{101} 对其的影响：样例 #1 的第一组测试数据阐释了这种情况：我们假定串是 \texttt{10110xxxxx}，经过一次变换之后变为 \texttt{100110xxxx}，不会有新的影响，不需要考虑。

由于 \texttt{110} 已经优先考虑，\texttt{101} 不继续考虑其影响。对于 \texttt{101010101\dots} 显然变换之后不会形成新的 \texttt{101}（有连续两个 \texttt{0}）。

综上所述：静态查询的方案是如果有子串 \texttt{110}，取其第一次出现的位置 i，答案是 n-i-1；如果有 \texttt{101}，答案是 1；否则答案是 0。

考虑如何动态修改——线段树维护即可。

需要维护节点的最前、后的一、二位信息，以便合并。标记是反转。查询直接对根节点信息考虑上述静态方案即可。代码有点长。

时间复杂度 O(t(n+q\log n))。

代码实现

#include<bits/stdc++.h>
#define int long long 
using namespace std;
constexpr int N=4e5+1,Inf=0x3f3f3f3f3f3f3f3fll;
int id,T,n,q,a[N],tot,rt,ans;
string s;
struct SegmentTreeNode{
    int l,r,ls,rs,pre0,pre1,suf0,suf1,pre00,pre01,pre10,pre11,suf00,suf01,suf10,suf11,is101,is010,first110,first001,tag;//101,110
    SegmentTreeNode(int l=0,int r=0):l(l),r(r),ls(0),rs(0),tag(0){
        pre0=pre1=suf0=suf1=pre00=pre01=pre10=pre11=suf00=suf01=suf10=suf11=0;
        is101=is010=0,first110=first001=Inf;
    }
}f[N<<1];
void pushup(int cur){
    f[cur].pre0=f[f[cur].ls].pre0,
    f[cur].pre1=f[f[cur].ls].pre1;
    f[cur].suf0=f[f[cur].rs].suf0,
    f[cur].suf1=f[f[cur].rs].suf1;
    f[cur].pre00=f[cur].pre01=f[cur].pre10=f[cur].pre11=f[cur].suf00=f[cur].suf01=f[cur].suf10=f[cur].suf11=0;
    f[cur].is101=f[cur].is010=0,f[cur].first110=f[cur].first001=Inf;
    if(f[cur].r-f[cur].l+1==1)
        return;
    if(f[f[cur].ls].r-f[f[cur].ls].l+1==1){
        f[cur].pre00=f[f[cur].ls].pre0&f[f[cur].rs].pre0,
        f[cur].pre01=f[f[cur].ls].pre0&f[f[cur].rs].pre1,
        f[cur].pre10=f[f[cur].ls].pre1&f[f[cur].rs].pre0,
        f[cur].pre11=f[f[cur].ls].pre1&f[f[cur].rs].pre1;
    }
    else{
        f[cur].pre00=f[f[cur].ls].pre00,
        f[cur].pre01=f[f[cur].ls].pre01,
        f[cur].pre10=f[f[cur].ls].pre10,
        f[cur].pre11=f[f[cur].ls].pre11;
    }
    if(f[f[cur].rs].r-f[f[cur].rs].l+1==1){
        f[cur].suf00=f[f[cur].ls].suf0&f[f[cur].rs].suf0,
        f[cur].suf01=f[f[cur].ls].suf0&f[f[cur].rs].suf1,
        f[cur].suf10=f[f[cur].ls].suf1&f[f[cur].rs].suf0,
        f[cur].suf11=f[f[cur].ls].suf1&f[f[cur].rs].suf1;
    }
    else{
        f[cur].suf00=f[f[cur].rs].suf00,
        f[cur].suf01=f[f[cur].rs].suf01,
        f[cur].suf10=f[f[cur].rs].suf10,
        f[cur].suf11=f[f[cur].rs].suf11;
    }
    f[cur].is101=f[cur].is010=0,f[cur].first110=f[cur].first001=Inf;
    if(f[cur].r-f[cur].l+1==2)
        return;
    f[cur].is101=(f[f[cur].ls].is101|f[f[cur].rs].is101),
    f[cur].is010=(f[f[cur].ls].is010|f[f[cur].rs].is010);
    if(f[f[cur].ls].suf1&&f[f[cur].rs].pre01||f[f[cur].ls].suf10&&f[f[cur].rs].pre1)
        f[cur].is101=1;
    if(f[f[cur].ls].suf0&&f[f[cur].rs].pre10||f[f[cur].ls].suf01&&f[f[cur].rs].pre0)
        f[cur].is010=1;
    f[cur].first110=min(f[f[cur].ls].first110,f[f[cur].rs].first110),
    f[cur].first001=min(f[f[cur].ls].first001,f[f[cur].rs].first001);
    if(f[f[cur].ls].suf11&&f[f[cur].rs].pre0)
        f[cur].first110=min(f[cur].first110,f[f[cur].ls].r-1);
    if(f[f[cur].ls].suf00&&f[f[cur].rs].pre1)
        f[cur].first001=min(f[cur].first001,f[f[cur].ls].r-1);
    if(f[f[cur].ls].suf1&&f[f[cur].rs].pre10)
        f[cur].first110=min(f[cur].first110,f[f[cur].ls].r);
    if(f[f[cur].ls].suf0&&f[f[cur].rs].pre01)
        f[cur].first001=min(f[cur].first001,f[f[cur].ls].r);
    return;
}
void flip(int cur){
    swap(f[cur].pre0,f[cur].pre1),swap(f[cur].suf0,f[cur].suf1);
    swap(f[cur].pre00,f[cur].pre11),swap(f[cur].pre01,f[cur].pre10),
    swap(f[cur].suf00,f[cur].suf11),swap(f[cur].suf01,f[cur].suf10);
    swap(f[cur].is010,f[cur].is101),swap(f[cur].first110,f[cur].first001);
    f[cur].tag^=1;
    return;
}
void pushdown(int cur){
    if(f[cur].tag){
        flip(f[cur].ls),flip(f[cur].rs);
        f[cur].tag^=1;
    }
    return;
}
void build(int l,int r,int&cur){
    f[cur=(++tot)]=SegmentTreeNode(l,r);
    if(l==r){
        if(a[l])
            f[cur].pre1=f[cur].suf1=1;
        else
            f[cur].pre0=f[cur].suf0=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void modify(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r)
        return flip(cur);
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        modify(l,r,f[cur].ls);
    if(mid<r)
        modify(l,r,f[cur].rs);
    return pushup(cur);
}
int query(){
    int tmp;
    if((tmp=f[rt].first110)!=Inf)
        return n-tmp-1;
    else if(f[rt].is101)
        return 1;
    else
        return 0;
}/*
void debug(){
    cerr<<query()<<' '<<f[rt].first001<<'\n';
    return;
}*/
void Main(){
    tot=0;
    cin>>n>>q>>s;
    for(int i=1;i<=n;i++)
        a[i]=(s[i-1]^48);
    build(1,n,rt);
    ans=query();
//    debug();
    for(int i=1,l,r;i<=q;i++){
        cin>>l>>r;
        modify(l,r,rt);
        ans^=(i+1)*query();
//        debug();
    }
    cout<<ans<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    for(cin>>id>>T;T;--T)
        Main();
    return 0;
}