题解：P13276 [NOI2025] 绝对防御

· · 题解

题解文字部分很长，知道大家不喜欢看，因此每一段我都会写下省流，有些部分你可以略读。

给一个（我场上胡的）单点修改线段树二分做法。时间复杂度与题目中的参数 3 无关（即改成任何数都一样），预处理线性，修改单 \log，求答案单 \log，因此总复杂度 O(n+q\log n)。

省流：给个比较优秀的做法，让大家见笑了。

先考虑一些暴力的做法。大部分人第一个想到的正确做法应该是二分答案再暴力 dp check。直接做是 O(qn^2\log n) 的，可以 bitset 优化但对正解没啥意义。有不少选手注意到了存在的连续段这个性质，可以获得 35\sim 40 pts。再往下就没有前途了，而我赛时可能代码能力不太够没写明白，干脆放弃了这个做法，去想下面的内容了。

省流：有一些暴力做法，不一定都对正解有帮助，所以我们接下来要取其精华。

首先保留刚才的二分结构，现在你二分到了 k，要判断其是否合法。我们先刻画出抽卡的结构。初始有 $每一轮你可以摸 1\sim 2 张牌，并打出一场攻击牌，一张防御牌或两张攻击牌。只有最后一次**可能**只摸 1 张，所以在每次摸牌前，你手里都**必然**有 k$ 张牌。

我们称每轮摸牌为一个回合，你需要挺过 t 个回合，其中前至少 t-1 个回合都是摸两牌。

省流：避免题目太玄幻，我们要用数学语言刻画下。

接下来，我们来定义几个数组变量：

设初始时的 $k$ 张牌中有 $h$ 张防御牌，则你能活下来，当且仅当存在一个序列 $c_{1\sim t}$ 表示每回合是否发动技能，满足： - $\forall 1\leq i\leq t,c_i\in \{0,1\}

省流：刻画完毕。

接下来我们稍微做做变形，设 s_i=c_1+\dots+c_i。不难证明，c_i 不会取到浮点数，下面我们只去刻画其上下界。四个条件可以分别这样改写：

省流：我们已经可以转成前缀和的差分约束限制了，因为只要判无解，所以找负环即可。

建出 t+1 个结点的图，则去除第一条和第四条限制的重复部分后，只剩了如下几种边：

称这四种边分别为一二三四类边。那么因为一四类边一定非负，不能只通过这类边搞出负环，所以一定要经过一次二三类边，因此一定要经过至少一次 0 号点。而我们只在意简单负环，也就是经过 0 号点恰好一次的环。

把二三类边经过的点记作关键点，则一四类边的作用是连接关键点，具体地，我们设 \operatorname{dist}(x,y) 表示从 x 只经过一四类边到达 y 的最短路，则有：

\operatorname{dist}(x,y)=\max(0,\lceil\dfrac{y-x}{z}\rceil)

接下来我们根据是否经过二三类边，把环分为三类，则限制有如下几类：

省流：成功得到极其好写的 O(qn^2\log n) 做法，前缀和优化就能得到小常数 O(qn\log n) 的 40pts 了，而且很有前途！

再做变形，\operatorname{dist}(x,y)=\lfloor\dfrac{\max(0,y-x+z-1)}{z}\rfloor，于是又能改写：

到这里已经很接近正解了，不过我们还有一些遗留问题。也就是说，我们每次二分一个 k 都要重新分回合，要维护的回合数量（也就是 t 的总和）是 O(n^2) 的，不就爆炸了吗？

此时你会注意到，阶段（即回合）本质不同只可能 k 的奇偶性不同，因此你只需要分两类，奇数开头还是偶数开头。

具体地，如果 n 是偶数，那么奇数开头的 d 序列为 122\dots221，偶数为 22\dots22。n 是奇数的话，奇数开头为 122\dots22，偶数开头为 22\dots221。

则二分的一个 k 代表的是，已经完成了前面的一些阶段，你要用线段树维护一段后缀的信息。

省流：你要根据 k 的奇偶性开两棵线段树，里面完全一样，所以只需要用结构体实现其中一个。下面讲线段树维护的具体细节，然后这个题就被成功解决了。

如果一起维护的话，开头位置就不是 0 了，设为 m 吧，则限制条件等价于。

第三四条，根据我们很早就提到的性质分别有：

因此可以分别改写为：

因此四个条件也就是：

省流：发现这个条件很像最大子段和状物，因此你类似小白逛公园地，单点修改并分别维护每个节点 (z\cdot l_i-1) 和 (-z\cdot r_i) 的和、最大前后缀和、最大子段和共八个变量即可。

每次二分 k，用树状数组算出 h，线段树查询后缀可以做到 O(n+q\log^2 n)。我考场就写的这玩意，在 selfEval 上最大点 1.6s，感觉稳了，没再优化下去。

赛后重新写了一遍，发现其实可以直接线段树二分，因为信息的可加性很强，也显然有二分性。树状数组省去了，代码极短，加上我的快读板子也只有 2.7K，下面是我的代码：

#include<bits/stdc++.h>
using namespace std;
namespace file_read{
    char ib[1<<25],*ip1=ib,*ip2=ib;
    inline char gc(){
        return ((ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin))),ip1==ip2?EOF:*ip1++);
    }
    inline int read(){
        int x=0;char c=gc();
        while(c<'0'||c>'9')c=gc();
        while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
        return x;
    }
    char ob[1<<25],*op=ob;
    inline void pc(char c){
        *op++=c;
    }
    void write(int x){
        if(x>=10)write(x/10);
        pc(x%10+'0');
    }
    void final_write(){
        fwrite(ob,op-ob,1,stdout);
    }
}
using namespace file_read;
int cc,T,n,q,s[400005];
struct pear{
    int hl,hr,h;
    int qdr,hdr;
    int mx1,mx2;
    int qdl,hdl;
}pp;
pear operator+(pear a,pear b){
    pear c;
    c.hl=a.hl+b.hl,c.hr=a.hr+b.hr,c.h=a.h+b.h;
    c.hdr=max(b.hdr,a.hdr+b.hr);c.qdr=max(a.qdr,a.hr+b.qdr);
    c.mx2=max(max(a.mx2,b.mx2),a.hdr+b.qdr);
    c.hdl=max(b.hdl,a.hdl+b.hl);c.qdl=max(a.qdl,a.hl+b.qdl);
    c.mx1=max(max(a.mx1,b.mx1),a.hdl+b.qdl);
    return c;
}
struct apple{
    int t,L[100005],R[100005],K[100005];
    void jjj(int l,int r){
        int b=s[l]+(l<r&&s[r]),a=r-l+1-b;
        ++t;L[t]=1-b,R[t]=a-1;K[t]=r;
    }
    pear sm[400005];
    void build(int l,int r,int o){
        if(l==r){
            sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
            sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
            sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
            sm[o].mx1=sm[o].mx2=-1e9;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,o<<1);build(mid+1,r,o<<1|1);
        sm[o]=sm[o<<1]+sm[o<<1|1];
    }
    void add(int l,int r,int o,int x){
        if(l==r){
            sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
            sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
            sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)add(l,mid,o<<1,x);
        else add(mid+1,r,o<<1|1,x);
        sm[o]=sm[o<<1]+sm[o<<1|1];
    }
    void jia(int x,int y){
        L[x]-=y;R[x]-=y;add(1,t,1,x);
    }
    void init(int a){
        t=0;jjj(1,a);
        for(int i=a+1,j;i<=n;j=min(n,i+1),jjj(i,j),i=j+1);
        build(1,t,1);
    }
    int query(int l,int r,int o){
        if(l==r)return K[l];
        pear qq=sm[o<<1|1]+pp;
        int mid=(l+r)>>1,k=K[mid],h=sm[1].h-qq.h;
        if(3*k<max(qq.mx1,qq.mx2)-2||3*h<qq.qdl-2||3*(k-h)<qq.qdr-2)
            return query(mid+1,r,o<<1|1);
        pp=qq;return query(l,mid,o<<1);
    }
    int suan(){
        pp.mx1=pp.mx2=-1e9;
        pp.hdl=pp.hdr=0;pp.qdl=pp.qdr=-1e9;
        pp.hl=pp.hr=pp.h=0;
        return query(1,t,1);
    }
}e0,e1;
void solve(){
    write(min(e0.suan(),e1.suan()));
}
int main(){
    cc=read(),T=read();
    while(T--){
        n=read(),q=read();
        for(int i=1;i<=n;++i){
            char c2=gc();
            while(c2<'0'||c2>'9')c2=gc();
            s[i]=c2-'0';
        }
        e0.init(2);e1.init(1);solve();
        while(q--){
            int x=read(),aa=(s[x]^1)-s[x];s[x]^=1;
            e0.jia((x+1)/2,aa);e1.jia(x/2+1,aa);
            pc(' ');solve();
        }
        pc('\n');
    }
    final_write();
    return 0;
}

省流：这题做完了。

接下来考虑加强，从几个方向考虑：

作者码字不易，花费很多心血，留个赞再走吧，谢谢！有错误请尽情指出，感激不尽！