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

· · 题解

题目传送门

提供一个需要用线段树维护 17 个变量的奶龙做法，赛时切了但是写和调的很痛苦，大概花了 3\operatorname{h}？

分析

复盘了我赛时的思路，感觉这题出的挺自然的，没有什么难想的点。

O(qn^2)

因为一定有 k\le n，所以按题意模拟就可以拿到 30 分。

特殊性质 A

相当于是一直在对字符串做右移操作，直至字符串是全 1 串就是不动点，所以答案就是 n-p，p 可以二分出来所以就做完了。

O(qn)+特殊性质 B

这个时候需要分析一下 f 函数在干什么，手动模拟几组小数据会发现我们可以只考虑局部性质 A，也就是考虑每个形如 1\cdots10\cdots0 的部分，其实只用考虑前缀 1 个数为 2 的串，就是形如 110\cdots0 的串（此处我们假设只有 1 的串也是合法串），我们记符合这样条件的字符串为合法串，此时 f 函数相当于对合法子串进行右移，每个合法子串的答案都可以当成性质 A 来做。

而且我们会发现若字符串出现若干个合法子串，那么我们只需要考虑第一个合法子串即可，因为它的答案不会被更前面的字符的变换所影响，毕竟答案只跟 1 和 0 的分界处有关，而 1 至少是两个所以无论前面是什么都影响不到，另一方面它的答案都大于后面每个合法子串的答案，所以直接取第一个合法字串的答案即可。

此时就会有人有疑问那万一第一个合法子串之前的字符变成“不动的”次数比第一个合法子串的答案要更大怎么办呢？其实我们会发现若一个字符串不存在合法子串，那么此时答案不会超过 1。考虑只有字符串中的 1 才可能使得后面的字符发生变换，而每个 1 之后一定是 0，那么此时若 0 之后是 0 则这个 1 不会对后面产生任何影响，而如果 0 之后是 1 那么最后的这个 1 就变为 0，所以至多变化一次就可以消除除了第一个 1 以外的所有 1（第一个 1 前面都是 0 所以一直不变满足条件），而至少变换一次的条件就变成了需要出现 101 这个子串。回到本段开头的问题，那么出现这样的情况就当且仅当字符串在第一个合法子串之前出现了 101 并且第一个合法子串只包含 1 这个字符（也就是形如 101111 的字符串需要特判），一个简单的解决方案是直接对两种情况的答案取 \max 即可。

闲话：笔者开始没有对两者取 \max，在 SelfEval 上获得了 75 分，并且无法通过样例 5 的第一组数据，后面又想了一会才想明白。

这样我们就可以 O(n) 求出一个字符串的 k 值，由于 B 性质翻转区间是整个区间所以字符串只有两种形态，故可以归为 q=2 的情形。

O(q\sqrt n)+特殊性质 C

赛时以为如果会了特殊性质 C 就可以拼上回滚莫队做到 95 分，结果发现还有修改显然做不了。

不过特殊性质 C 理应是不难的，因为是否出现合法子串是单调的，顺着扫一遍就做完了。注意每次修改的部分都是一个前缀，所以这个性质是对的，只不过要多记一个 0 为前缀的合法子串位置。

至于分块做法是赛后 lhy 告诉我的，貌似块内暴力找合法位置比线段树好实现的多。

O(q\log n)

我们只关注字符串中的第一个连续超过两个 1 的子串结尾位置和是否存在 101，而由于有区间翻转操作则还需要存储第一个连续超过两个 0 的子串结尾位置和是否存在 010 即可，这部分用线段树是可以做的，但是我的实现相当丑。

代码实现

对于每个变量都给了注释，不过赛后复盘又打了一遍自己考场上的史山代码很难受。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10;
int C,T,n,q;
ll ans;
char a[N];

//这个结构体是存储0或者1对应的变量，以1为注释，0也是类似的
struct node{
    bool pd,ok;//pd表示是否存在合法串，ok表示是否存在101
    int op,nh,nt;//op表示第一个合法串中第一个0的出现位置，nh表示区间开头连续1的数量，nt表示区间结尾连续1的数量
    void cl(){pd=ok=0;op=nh=nt=0;}//初始化函数
};

struct Seg{
    node c[2];//c[0]存0相关信息，c[1]存1相关信息
    int f,l,r,b1,b2,e2,e1;//f是标记，l和r表示区间的范围，b1、b2表示区间开头两个字符（b1是第一个b2是第二个），e1、e2表示区间结尾两个字符（e1是倒数第一个，e2是倒数第二个），不存在用-1表示
    void cl(){c[0].cl(),c[1].cl(),f=0,b1=b2=e1=e2=-1;}//初始化函数
    void tt(int _b1,int _b2,int _e2,int _e1){b1=_b1,b2=_b2,e2=_e2,e1=_e1;}//赋值函数
    void tag()
    {
        f^=1;
        if(b1!=-1) b1^=1;
        if(b2!=-1) b2^=1;
        if(e2!=-1) e2^=1;
        if(e1!=-1) e1^=1;
        swap(c[0],c[1]);
    }//区间翻转函数
    friend Seg operator+(Seg x,Seg y)
    {
        Seg res;res.cl();
        int len1=x.r-x.l+1,len2=y.r-y.l+1;
        for(int i=0;i<2;i++)
        {
            node &rr=res.c[i];
            node xx=x.c[i],yy=y.c[i];
            if(xx.pd&&xx.op<=x.r) rr.pd=1,rr.op=xx.op;//合法串出现在左边
            else if(xx.nt+yy.nh>1) rr.pd=1,rr.op=y.l+yy.nh;//拼在一起出现合法串
            else if(yy.pd) rr.pd=1,rr.op=yy.op;//合法串出现在右边
            rr.nh=xx.nh+(xx.nh==len1?yy.nh:0);
            rr.nt=yy.nt+(yy.nt==len2?xx.nt:0);
            rr.ok=xx.ok|yy.ok;//左右是否存在101或者010
            if(len1>=2&&x.e2==i&&x.e1==(i^1)&&y.b1==i) rr.ok=1;
            if(len2>=2&&x.e1==i&&y.b1==(i^1)&&y.b2==i) rr.ok=1;//拼在一起是否出现101或010
        }
        if(len1==1)
        {
            if(len2==1) res.tt(x.b1,y.b1,x.b1,y.b1);
            else res.tt(x.b1,y.b1,y.e2,y.e1);
        }
        else
        {
            if(len2==1) res.tt(x.b1,x.b2,x.e1,y.e1);
            else res.tt(x.b1,x.b2,y.e2,y.e1);
        }//这里要分类讨论，因为不一定存在b2和e2
        res.l=x.l,res.r=y.r;
        return res;
    }//区间合并函数
}tr[N<<2];

void pushup(int k)
{
    int f=tr[k].f;
    tr[k]=tr[k<<1]+tr[(k<<1)|1];
    tr[k].f=f;
}

void down(int k)
{
    if(!tr[k].f) return;
    tr[k<<1].tag(),tr[(k<<1)|1].tag();
    tr[k].f=0;
}

void build(int k,int l,int r)
{
    tr[k].cl(),tr[k].l=l,tr[k].r=r;
    if(l==r)
    {
        int ch=a[l]-'0';
        tr[k].b1=tr[k].e1=ch;
        tr[k].c[ch].nh=tr[k].c[ch].nt=1;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid),build((k<<1)|1,mid+1,r);
    pushup(k);
}

void update(int k,int l,int r,int a,int b)
{
    if(a<=l&&b>=r)
    {
        tr[k].tag();
        return;
    }
    down(k);
    int mid=(l+r)>>1;
    if(a<=mid) update(k<<1,l,mid,a,b);
    if(b>mid) update((k<<1)|1,mid+1,r,a,b);
    pushup(k);
}

void solve(int i)
{
    node res=tr[1].c[1];
    int k=0;
    if(res.op) k=max(k,n-res.op+1);
    if(res.ok) k=max(k,1);//记得取max
    ans^=1ll*(i+1)*k;
}

int main()
{
    scanf("%d%d",&C,&T);
    while(T--)
    {
        scanf("%d%d%s",&n,&q,a+1);
        a[n+1]='2';ans=0;
        build(1,1,n);solve(0);
        for(int _i=1,l,r;_i<=q;_i++)
        {
            scanf("%d%d",&l,&r);
            update(1,1,n,l,r);solve(_i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}