原发布于2020-01-14。

upd 2020-04-10: 代码写错了，被hack了，已更正

link

网上大多数都是$O(n\log^2 n)$的，不过我做法是$O(n\log n)$的...

题解

首先考虑没有$k$限制的情况（或者说加完之后）如何判断$l,r$是否可以办比赛。

将题意中的$g_i$用$a_i$表示，$w_i$用$b_i$表示。

设$f_i=f_{i-1}+a_{i-1}-b_{i-1},g_i=g_{i-1}+b_{i-1}-a_i$。

那么$l,r$可以办比赛当且仅当
$$f_l=\min _{l\leq i \leq r} f_i,g_r=\min _{l\leq i \leq r} g_i$$

那么考虑有$k$限制的情况。

如果$a_i+1$，那么对于$i\lt j,f_j=f_j+1$,对于$i\le j,g_j=g_j-1$

从$n$到$1$枚举$l$，设单调栈为$f_l\gt f_{x_1}\gt f_{x_2}\gt f_{x_3}\ldots(l\lt x_1\lt x_2\lt x_3\ldots)$

那么为了$l$到$r$满足条件，肯定是$a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}$对于i升序一个一个执行直到$l$能到$r$，其中$x_0=l$

接下来考虑$r$到$l$。

设$h_i$为做完$a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}$后的$g_i$,

显然剩下的$a_i$增加都要给$a_r$，那么$r$能到$l$当且仅当$g_r-k\leq h_i,l\le i\lt r$

如果对于$i\le l$定义$h_i=\infty$，那么就是$g_r-k\leq h_i,i\lt r$

可以在单调栈二分出$r$的上界，然后在线段树上二分得到最大可行$r$。

时间复杂度$O(n\log n)$。

代码

已define int long long

int a[100005],b[100005],f[100005],g[100005];
int s[100005],t;
int n,k;
struct smt{
    int amn,bmn,atg;    
    int ls,rs;
    smt *l,*r;
    smt(int la,int ra){
        amn=inf;bmn=-inf;
        atg=0;
        ls=la;rs=ra;
        if(ls==rs){
            l=r=0;
        }
        else{
            int mid=(ls+rs)>>1;
            l=new smt(ls,mid);
            r=new smt(mid+1,rs);
        }
    }
    void setg(int x){
        if(ls==rs){
            amn=bmn=g[x];    
            return;
        }
        if(x<=l->rs)l->setg(x);
        else r->setg(x);
        amn=min(l->amn,r->amn);
        bmn=min(l->bmn,r->bmn);
    }
    void push_down(){
        l->atg+=atg;
        l->amn+=atg;
        r->atg+=atg;
        r->amn+=atg;
        atg=0;
    }
    void add(int la,int ra,int w){
        if(la<=ls && rs<=ra){
            atg+=w;amn+=w;
            return;
        }
        push_down();
        if(la<=l->rs)l->add(la,ra,w);
        if(ra>=r->ls)r->add(la,ra,w);
        amn=min(l->amn,r->amn);
    }
    int query(int x,int rm){
        if(ls>rm)return 0;
        if(bmn-k>x)return 0;//没加这一句话会错
        if(ls==rs)return ls;
        push_down();
        if(min(x,l->amn)>=r->bmn-k){
            int ans=r->query(min(x,l->amn),rm);
            if(ans)return ans;
        }
        return l->query(x,rm);
    }
};
smt *rt;
signed main(){
#ifdef QAQAutoMaton 
    freopen("E.in","r",stdin);
    freopen("E.out","w",stdout);
#endif
    read(n,k);
    rt=new smt(1,n);
    for(int i=1;i<n;++i)read(b[i]);
    for(int i=1;i<=n;++i)read(a[i]);
    for(int i=1;i<=n;++i){
        f[i]=f[i-1]+a[i-1]-b[i-1];
    }
    for(int i=1;i<=n;++i){
        g[i]=g[i-1]+b[i-1]-a[i];
    }
    int ans=0;
    for(int i=n;i;--i){
        rt->setg(i);
        while(t && f[s[t]]>=f[i]){
            if(t>1){
                rt->add(s[t-1]-1,n,f[s[t]]-f[s[t-1]]);
            }
            --t;
        }
        s[++t]=i;
        if(t>1){
            rt->add(s[t-1]-1,n,f[s[t-1]]-f[s[t]]);
        }

        s[0]=n+1;

        int l=1,r=t,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(f[i]-f[s[mid]]<=k)r=mid-1;
            else l=mid+1;
        }
        chkmax(ans,rt->query(inf,s[r]-1)-i+1);
    }
    write(ans,'\n');
    return 0;
}

标签: 单调栈

添加新评论