题解：P13274 [NOI2025] 三目运算符

· · 题解

大家好，不知道场内还是场外人员前来写题解。

场上最后 30 分钟才看题的，但是没时间细想。不难发现有且仅有 \texttt{110} 或者 \texttt{101} 这两种子串会改变原串。也就是说，我们要求的最终的那个不动点必须满足没有这两个子串。

先考虑只有 \texttt{110} 的情况，操作后将会变为 \texttt{111}，可以看作是原先的 1 的长度 \ge2 的连续段向后增加了一个 1。但是如果增加到了后面的一个 1 的连续段，那么就会出现 \texttt{101} 的形状，这时我们再来讨论。

考虑 \texttt{1101} 的情况，操作后将会变为 \texttt{1110}，可以看作是后一个 1 的连续段的最开头的 1 与前面那个 0 换了个位置。

让我们再来看一个比较普通的情况，整个串的每个 1 的连续段长度都 \ge2。根据上面两条结论，请读者自行脑补一个动画：

在两个 1 的连续段相隔一个 0 以上时，前面一个串将会向后扩张，不断加上一个 1；
当相隔一个 0 时，这个 0 将会跟后面的那个 1 交换位置，视觉上就是这个 0 向后移了一位，也可以说是前面的 1 的连续串继续扩张，后面那个 1 的连续段整体向后平移了一位。

经过与这样的模拟，我们不难发现其实要到达无法改变的状态（即不动点），取决于最开始的那个 110 在哪。

当然我们还没有考虑只是 \texttt{101} 的情况。如果是 \texttt{1101} 中的，那么随着修改，\texttt{110} 和 \texttt{101} 一定是同时存在的。否则单独的这个东西只可以操作一次，变为 \texttt{100}。

综上，我们可以得出的结论是：

所以我们只要维护第一个 \texttt{110} 的位置，以及判断 \texttt{101} 是否存在即可。对于前者，我们只需要维护 1 的连续段，找到第一个长度 \ge2 的连续段即可；对于后者，记录区间最靠两端的 1 的位置去做即可。

至于区间反转，再记录一下 0 的情况即可。

码还没写，写完了贴出来，退役久了估计这个题得写个两三个小时的，快进到题解通道关了。

时间复杂度 \mathcal{O}(n\log n)。

upd 2025.10.25

代码咕到现在了。发现以前嘴的实现不如这种更直观好写：

节点上记录 11 个信息，区间最左边两个的值，最右边两个的值，第一个 \texttt{110}/\texttt{001} 出现的位置，是否存在 \texttt{101}/\texttt{010}，区间的左右端点以及一个反转的 tag。合并区间答案参考代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,l,r) for(int i=l;i<=r;i++)
#define F_(i,r,l) for(int i=r;i>=l;i--)
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define mid ((l+r)>>1)
#define SZ(a) ((int)(a).size())
#define pc putchar

const int mod = 998244353;
const int INF = 1e18;
const int N = 4e5 + 5;

void cmx(int&a,int b){
    a=max(a,b);
}
void cmn(int&a,int b){
    a=min(a,b);
}
void add(int&a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int rd(){
    int x=0,y=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-')y=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return x*y;
}

int n,q,a[N];

struct node{
    int l1,l2,r1,r2,p,pp,l,r;
    bool fl,fl1;
    friend node operator+(const node &a,const node &b){
        node c;
        if(a.r-a.l==0){
            c=(node){a.l1,b.l1,b.l1,a.l1,INF,INF,a.l,b.l,0,0};
        }else{
            if(b.r-b.l==0){
                c.l1=a.l1,c.l2=a.l2;
                c.r1=b.r1,c.r2=a.r1;
            }else{
                c.l1=a.l1,c.l2=a.l2;
                c.r1=b.r1,c.r2=b.r2;
            }
            c.l=a.l,c.r=b.r;

            if(a.p!=INF){
                c.p=a.p;
            }else if(a.r2==1&&a.r1==1&&b.l1==0){
                c.p=b.l;
            }else if(a.r1==1&&b.l1==1&&b.l2==0){
                c.p=b.l+1;
            }else c.p=b.p;
            c.fl=a.fl|b.fl;
            if(a.r2==1&&a.r1==0&&b.l1==1||a.r1==1&&b.l1==0&&b.l2==1)
                c.fl=1;

            if(a.pp!=INF){
                c.pp=a.pp;
            }else if(a.r2==0&&a.r1==0&&b.l1==1){
                c.pp=b.l;
            }else if(a.r1==0&&b.l1==0&&b.l2==1){
                c.pp=b.l+1;
            }else c.pp=b.pp;
            c.fl1=a.fl1|b.fl1;
            if(a.r2==0&&a.r1==1&&b.l1==0||a.r1==0&&b.l1==1&&b.l2==0)
                c.fl1=1;
        }
        return c;
    }
};

struct SGT{
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    node tr[N<<2];
    int tg[N<<2];
    void apl(int rt){
        tr[rt].l1^=1;
        tr[rt].l2^=1;
        tr[rt].r1^=1;
        tr[rt].r2^=1;
        swap(tr[rt].p,tr[rt].pp);
        swap(tr[rt].fl,tr[rt].fl1);
    }
    void pu(int rt){
        tr[rt]=tr[ls]+tr[rs];
    }
    void pd(int rt){
        if(tg[rt]){
            apl(ls),apl(rs);
            tg[ls]^=1,tg[rs]^=1;
            tg[rt]=0;
        }
    }
    void bd(int l,int r,int rt){
        tg[rt]=0;
        if(l==r){
            int x=a[l];
            tr[rt]=(node){x,INF,x,INF,INF,INF,l,r,0,0};
            return;
        }
        bd(l,mid,ls);
        bd(mid+1,r,rs);
        pu(rt);
        // cerr<<l<<' '<<r<<' '<<tr[rt].l1<<' '<<tr[rt].l2<<' '<<tr[rt].r1<<' '<<tr[rt].r2<<' '<<tr[rt].p<<'\n';
    }
    void upd(int l,int r,int rt,int ql,int qr){
        if(ql<=l&&r<=qr){
            apl(rt),tg[rt]^=1;
            return;
        }
        pd(rt);
        if(ql<=mid)
            upd(l,mid,ls,ql,qr);
        if(mid+1<=qr)
            upd(mid+1,r,rs,ql,qr);
        pu(rt);
    }
}T;

string s;

int ans;

void get(int x){
    // cerr<<x<<'!'<<'\n';
    if(T.tr[1].p!=INF){
        // cerr<<n-T.tr[1].p+1<<'\n';
        ans^=(n-T.tr[1].p+1)*(x+1);
    }else if(T.tr[1].fl){
        // cerr<<1<<'\n';
        ans^=x+1;
    }
}

void SOLVE(){
    n=rd(),q=rd();
    ans=0;
    cin>>s;
    F(i,1,n){
        a[i]=s[i-1]-'0';
    }
    T.bd(1,n,1);
    get(0);
    F(i,1,q){
        int l=rd(),r=rd();
        T.upd(1,n,1,l,r);
        get(i);
    }
    printf("%lld\n",ans);
    return;
}
signed main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    int c=rd(),T=rd();
    while(T--)SOLVE();
    return 0;
}

广告