绝对防御 NOI2025

[NOI2025] 绝对防御

妙妙题。

NOI 2025 。

小 Q 在与电脑玩一款名为“绝对防御”的回合制卡牌游戏。

小 Q 有一个大小为 $n$ 的牌堆，包含两种牌：攻击牌与防御牌。游戏开始时，小 Q 会从牌堆顶抽取 $k \ (1 \leq k \leq n)$ 张牌作为初始手牌，接下来他会与电脑进行若干轮对战。

每轮对战开始时，小 Q 从牌堆顶抽取 $2$ 张牌。特别地，若牌堆只剩余 $1$ 张牌，则小 Q 只抽取 $1$ 张。一轮对战分为两个回合：

• 第一回合：小 Q 为攻击方，电脑为防御方；
• 第二回合：小 Q 为防御方，电脑为攻击方。

在每回合中，攻击方必须从手牌中选择一张攻击牌进行攻击，防御方必须从手牌打出一张防御牌进行防御。无法按要求出牌者立即判负。

电脑的攻击牌与防御牌都是无限的，即电脑总能打出对应牌。为平衡电脑的实力，小 Q 可以使用一种特殊技能：当小 Q 为防御方时，他可以从手牌打出一张攻击牌进行防御。该技能每 $3$ 轮对战才能使用一次，即在某轮使用技能后，接下来的 $2$ 轮对战中不能使用该技能。

在给定规则下，小 Q 的获胜目标为在电脑猛烈攻击中幸存，即在某轮对战结束后，牌堆被抽空。特别地，若游戏开始时牌堆已被抽空，则小 Q 直接达成获胜目标。小 Q 想知道最小的初始抽牌数 $k$，使得他能达成胜利目标。

小 Q 觉得这个问题过于简单，因此他增加了 $q$ 次修改操作。第 $i \ (1 \leq i \leq q)$ 次修改操作给定一个正整数 $x_i$，改变牌堆顶到牌堆底的第 $x_i$ 张牌的类型，即将攻击牌变为防御牌，将防御牌变为攻击牌。你需要对初始牌堆及每次修改后的牌堆，求出最小的小 Q 初始抽牌数 $k$，使得小 Q 能达成胜利目标。

设 $0$ 为攻击牌， $1$ 为防御牌。

首先 $k$ 满足可二分性，于是问题变为判定一个 $k$ 是否合法。

如果你此时想贪心的：有 $1$ 就用 $1$ ，否则用 $0$ 。那么恭喜你止步于此，因为这个很难刻画。

然后有一个惊为天人的思路：

令 $a_i,b_i,c_i$ 分别表示第 $i$ 轮对战获得的 $0$ 的个数， $1$ 的个数以及使用技能的次数。

令 $A_i,B_i,C_i$ 分别表示 $a,b,c$ 的前缀和。

令 $X,Y$ 表示初始 $k$ 张牌的 $0$ 的个数和 $1$ 的个数。

则题目的所有限制可以表示为：

• 对于任意的 $i$ ， $X+A_i\ge i+C_i$ 。
• 对于任意的 $i$ ， $Y+B_i\ge i-C_i$ 。
• 对于任意的 $i\le j$ ， $0\le C_j-C_i\le \lceil\frac{j-i}{3}\rceil$ 。
• 对于任意的 $i$ ， $C_i\ge 0$ 。

然后我们得出结论：

$$i-Y-B_i\le C_i\le X+A_i-i$$

令 $L_i=i-Y-B_i$ ， $R_i=X+A_i-i$

结合其他的限制可以进行差分约束建图： 自己画 .png 。

那么有解的条件就是图不存在负环。

观察一下可以发现如下四个负环存在的条件（任意一个满足即有负环）：

• 存在 $i\le j$ ， $-L_i+R_i<0$ 。
• 存在 $i\le j$ ， $R_i-L_j+\lceil\frac{j-i}{3}\rceil<0$ 。
• 存在 $i$ ， $R_i<0$ 。
• 存在 $i$ ， $L_i>\lceil\frac{i}{3}\rceil$ 。

我们依次来这四个条件：

Case #1

将 $L_i,R_j$ 展开，得：

$$X+Y+B_i-i+A_j-j$$

注意到 $A_i+B_i=2i$ ，则：

$$X+Y+(i-A_i)+(A_j-j)$$

然后关键的一步：将 $A_i-i$ 看作是 $p_i=a_i-1$ 的前缀和，则原式左侧相当于要求：序列 $p_i$ 的最小子段和，使用线段树即可动态维护。

Case #2

同上，得：

$$X+Y+A_i-i+B_j-j+\lceil\frac{j-i}{3}\rceil<0$$

其中最烦的是这个 $\lceil\frac{j-i}{3}\rceil$ ，我们考虑如何消掉这个条件。

注意到如下变换：

$$N+\lceil\frac{M}{3}\rceil<0\\\lceil\frac{M}{3}\rceil<-N\\\lceil\frac{M}{3}\rceil\le -N-1\\\frac{M}{3}\le -N-1\\M\le -3N-3\\ 3N+M+3\le 0\\3N+M+2<0$$

这样就把向上取整消去了。代入后得到：

$$(3X+3Y+2)-3B_i+3B_j+2i-2j<0$$

同样的，令 $q_i=3b_i-2$ ，则 $-3B_i+3B_j+2i-2j$ 也可以看作一个 $q$ 的区间和。于是我们只需要求最小子段和就行。

Case #3,4 同理，只需要最小前缀和即可。

总结

然后只需要模拟上述过程就行，然而还有一个问题。

可以发现 $a,b$ 事实上并不确定：他们有 $n-k$ 的奇偶性经行确定。

于是我们要对 $n-k$ 的奇偶性分开考虑。也就是说，我们总共要维护四棵线段树，分别是 $p0,q0,p1,q1$ 。

代码十分复杂，不过没有什么细节，十分好写：

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m;
struct node{int lm,rm,tm,num;};
node operator+(node l,node r){
    node p;
    p.num=l.num+r.num;
    p.lm=min(l.lm,l.num+r.lm);
    p.rm=min(r.rm,r.num+l.rm);
    p.tm=min({l.tm,r.tm,l.rm+r.lm});
    return p;
}
struct SEG{
    node a[N<<2];
    void build(int p,int l,int r,int *b){
        if(l==r){
            int t=min(0,b[l]);
            a[p]={t,t,t,b[l]};
            return ;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid,b);
        build(p<<1|1,mid+1,r,b);
        a[p]=a[p<<1]+a[p<<1|1];
    }
    void insert(int p,int l,int r,int x,int y){
        if(!x)return ;
        if(l==r){
            int t=min(0,y);
            a[p]={t,t,t,y};
            return ;
        }
        int mid=(l+r)>>1;
        if(mid>=x)insert(p<<1,l,mid,x,y);
        else insert(p<<1|1,mid+1,r,x,y);
        a[p]=a[p<<1]+a[p<<1|1];
    }
    node query(int p,int l,int r,int ql,int qr){
        if(ql>qr)return {0,0,0,0};
        if(ql<=l&&r<=qr)return a[p];
        int mid=(l+r)>>1;
        if(mid>=ql&&mid<qr)return query(p<<1,l,mid,ql,qr)+query(p<<1|1,mid+1,r,ql,qr);
        if(mid>=ql)return query(p<<1,l,mid,ql,qr);
        return query(p<<1|1,mid+1,r,ql,qr);
    }
}P0,P1,Q0,Q1;
struct BIT{
    int c[N];
    void clear(){for(int i=1;i<=n;i++)c[i]=0;}
    void add(int x,int y){for(;x<=n;x+=(x&-x))c[x]+=y;}
    int query(int x,int cnt=0){for(;x>=1;x-=(x&-x))cnt+=c[x];return cnt;}
}B0,B1;
int a[N],tot0,tot1,id0[N],id1[N],a0[N],a1[N],b0[N],b1[N];
int p0[N],q0[N],p1[N],q1[N];
void init(){
    B0.clear(),B1.clear();
    for(int i=1;i<=n;i++)a0[i]=a1[i]=b0[i]=b1[i]=0;
    for(int i=1;i<=n;i++){
        if(a[i])B1.add(i,1);
        else B0.add(i,1);
    }
    tot0=tot1=0;
    for(int i=n;i>=1;i-=2)tot0++;
    for(int i=n+1;i>=1;i-=2)tot1++;
    int t1=tot1,t0=tot0;
    for(int i=n;i>=1;i-=2)id0[i]=id0[i-1]=t0,t0--;
    for(int i=n+1;i>=1;i-=2)id1[i]=id1[i-1]=t1,t1--;
    for(int i=1;i<=n;i++){
        if(a[i])b0[id0[i]]++,b1[id1[i]]++;
        else a0[id0[i]]++,a1[id1[i]]++;
    }
    for(int i=1;i<=tot0;i++)p0[i]=a0[i]-1,q0[i]=3*b0[i]-2;
    for(int i=1;i<=tot1;i++)p1[i]=a1[i]-1,q1[i]=3*b1[i]-2;
    P0.build(1,1,tot0,p0);
    P1.build(1,1,tot1,p1);
    Q0.build(1,1,tot0,q0);
    Q1.build(1,1,tot1,q1);
}   
void update(int x){
    if(a[x]==0){
        B0.add(x,-1);
        B1.add(x,1);
        a0[id0[x]]--,a1[id1[x]]--;
        b0[id0[x]]++,b1[id1[x]]++;
    }
    else{
        B0.add(x,1);
        B1.add(x,-1);
        a0[id0[x]]++,a1[id1[x]]++;
        b0[id0[x]]--,b1[id1[x]]--;
    }
    a[x]^=1;
    p0[id0[x]]=a0[id0[x]]-1;
    p1[id1[x]]=a1[id1[x]]-1;
    q0[id0[x]]=3*b0[id0[x]]-2;
    q1[id1[x]]=3*b1[id1[x]]-2;
    P0.insert(1,1,tot0,id0[x],p0[id0[x]]);
    P1.insert(1,1,tot1,id1[x],p1[id1[x]]);
    Q0.insert(1,1,tot0,id0[x],q0[id0[x]]);
    Q1.insert(1,1,tot1,id1[x],q1[id1[x]]);
}
bool check0(int k){
    if(k==n)return 0;
    int id=id0[k+1];
    int t1=P0.query(1,1,tot0,id,tot0).tm;
    int t2=Q0.query(1,1,tot0,id,tot0).tm;
    int t3=P0.query(1,1,tot0,id,tot0).lm;
    int t4=Q0.query(1,1,tot0,id,tot0).lm;
    int X=B0.query(k),Y=B1.query(k);
    return X+Y+t1<0||3*X+3*Y+2+t2<0||X+t3<0||3*Y+2+t4<0;
}
bool check1(int k){
    int id=id1[k+1];
    int t1=P1.query(1,1,tot1,id,tot1).tm;
    int t2=Q1.query(1,1,tot1,id,tot1).tm;
    int t3=P1.query(1,1,tot1,id,tot1).lm;
    int t4=Q1.query(1,1,tot1,id,tot1).lm;
    int X=B0.query(k),Y=B1.query(k);
    return X+Y+t1<0||3*X+3*Y+2+t2<0||X+t3<0||3*Y+2+t4<0;
}
int query(){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if((n-mid)&1){if(!check1(mid))r=mid;else l=mid+1;}
        else {if(!check0(mid))r=mid;else l=mid+1;}
    }
    return l;
}
void WZH(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%1d",a+i);
    init();
    printf("%d ",query());
    while(m--){
        int x;
        scanf("%d",&x);
        update(x);
        printf("%d ",query());
    }
    puts("");
}
int main(){
    int T,cid;
    scanf("%d%d",&cid,&T);
    while(T--)WZH();
    return 0;
}