题解：P8304 [CoE R4 D] 01 串

· · 题解

P8304 [CoE R4 D] 01 串

Problem
Blog

披着数据结构外衣的贪心。

第一篇题解已经把后面数据结构部分讲的很清楚了，但贪心的正确性并未证明。这里补上。

首先用 -1 替换原串中的 0，设得到的数列为 \{a_i\}，则原来的条件转化为它的前后缀和均非负。为了得到满足要求的子序列，我们要删去一些元素，而且显然不应该删去 1，只会删去某些 -1。

对于一个前缀 L\sim i，里面删去 -1 的个数至少要是 \max\{-\operatorname{pre}_i,0\}。同样对于 i\sim R，至少要删去 \max\{-\operatorname{suf}_i,0\} 个 -1，其中 \operatorname{pre}_i 和 \operatorname{suf}_i 为前后缀和。

那么我们得到了删去 -1 数量的一个下界：

\begin{aligned} ans&\ge \max_{L\leq i<j\leq R}\{-\operatorname{pre}_i-\operatorname{suf}_j\}\\ \end{aligned}

而再考虑贪心策略：正着跑一遍，统计当前和，和小于 0 就删去这个 -1，再反着跑同样过程。

正着跑的时候跑到 x 时，删去的 -1 数为 \displaystyle\max_{i\leq x}\{-\operatorname{pre}_i\}，跑完后，后缀和因删除操作而变成了 \operatorname{suf'}_i（为了方便这里仍然保留被删去的那些数的下标）。

而 \operatorname{suf'}_i 相比原来增加了，增量为 i 右边被删去的 -1 数，也就是总删去数减去左边删去的个数。即：

\operatorname{suf'}_i=\operatorname{suf}_i+\max_{L\leq k\leq R}\{-\operatorname{pre}_k\}-\max_{L\leq k<i}\{-\operatorname{pre}_k\}

反着跑新增的删去数为 \max\{-\operatorname{suf'}_i\}，一共删去的数是两次之和，可以化简为

\begin{aligned} &\max_i\{-\operatorname{suf}_i-\max_{L\leq k\leq R}\{-\operatorname{pre}_k\}-\min_{L\leq k<i}\{-\operatorname{pre}_k\}\}+\max_{i\leq x}\{-\operatorname{pre}_i\}\\ =&\max_{L\leq k<i\leq R} \{-\operatorname{pre}_k-\operatorname{suf}_i\} \end{aligned}

这是该贪心算法的删去次数的严格表达式，可以发现它恰好等于理论下界，即它就是最优解。而上式为区间和减去最大子段和，线段树维护即可。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

template <typename T>
void Read(T &x) {
    x=0;char c=getchar();
    T f=1;
    while(c<'0'||c>'9'){ if(c=='-'){f=-1;} c=getchar(); }
    x=c-'0';
    while((c=getchar())>='0' && c<='9'){ x=x*10+c-'0';}
    x*=f;
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
    Read(x);
    Read(args...);
}

const int maxn=500005;
struct node{
    int s,l,r,t;
    int m;
    node(){}
    node(int v){
        s=v;l=r=t=v;
        m=v;
    }
};

node v[maxn*4+10],a[maxn];
void pushup(node&x,const node&l,const node&r){
    x.s=l.s+r.s;
    x.l=max(l.l,l.s+r.l);
    x.r=max(r.r,r.s+l.r);
    x.t=max(l.t,max(r.t,l.r+r.l));
    x.m=max(l.m,r.m);
}
void build(node a[],int l,int r,int id){
    if(l==r){
        v[id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(a,l,mid,id<<1);
    build(a,mid+1,r,id<<1|1);
    pushup(v[id],v[id<<1],v[id<<1|1]);
}
node query(int x,int y,int id,int l,int r){
    if(x<=l && r<=y){
        return v[id];
    }
    int mid=(l+r)>>1;
    node res(-0x3f3f3f);
    if(x>mid){
        return query(x,y,id<<1|1,mid+1,r);
    }else if(y<=mid){
        return query(x,y,id<<1,l,mid);
    }else{
        pushup(res,query(x,y,id<<1,l,mid),query(x,y,id<<1|1,mid+1,r));
    }
    return res;
}
void change(int p,node x,int id,int l,int r){
    if(l==r){
        v[id]=x;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid){
        change(p,x,id<<1,l,mid);
    }else{
        change(p,x,id<<1|1,mid+1,r);
    }
    pushup(v[id],v[id<<1],v[id<<1|1]);
}

int main(){

    int n,q;
    Read(n,q);
    for(int i=1;i<=n;i++){
        char ch;cin>>ch;
        a[i].s=ch-'0';
        if(a[i].s==0) a[i].s=-1;
        a[i].l=a[i].r=a[i].t=a[i].s;
        a[i].m=a[i].s;
    }
    build(a,1,n,1);
    for(int i=1;i<=q;i++){
        int l,r;
        Read(l,r);
        auto t=query(l,r,1,1,n);
        if(t.t<0) t.t=0;
        if(t.t-t.s>=r-l+1) cout<<"-1\n";
        else cout<<(r-l+1-(t.t-t.s))<<"\n";
    }

    return 0;
}