自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 23:11:33，当前版本为作者最后更新于2025-03-27 21:14:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个很简洁的做法。

先思考如何判断一个区间 $[l,r]$ 是否合法。显然我们会给 $[l,r]$ 内的下标全选 $b$，其余下标全选 $a$。条件无非三个：

• $[l,r]$ 任意缩一段前缀 / 后缀，不会因为这段前缀 / 后缀和 $<0$ 而变大；

• $[l,r]$ 任意扩展一段前缀 / 后缀，不会因为这段前缀 / 后缀和 $>0$ 而变大；

• $[1,l-1]$ 和 $[r+1,n]$ 内的 $a$ 最大子段和 $\le b[l,r]$ 的和。

我们发现第三个条件可以直接考虑全局非空的 $a$ 最大子段和，因为 $b$ 的限制在中间那段只会更紧。

形式化地描述，我们需要满足：（设 $s$ 为 $b$ 的前缀和数组）

• $\forall i \in [l,r], s_r-s_{l-1}\ge s_i-s_{l-1}$，即 $s_r$ 是 $s[l,r]$ 的最大值；
• $\forall i \in [l,r], s_r-s_{l-1}\ge s_{r}-s{i-1}$，即 $s_{l-1}$ 是 $s[l-1,r-1]$ 的最小值；
• $pre_{l-1}=0$，其中 $pre_i$ 表示 $a[1,i]$ 的最大子段和；
• $suf_{r+1}=0$，其中 $suf_i$ 表示 $a[i,n]$ 的最大子段和；
• $s_r-s_{l-1}\ge M$，其中 $M$ 表示 $a$ 序列的最大非空子段和。

考虑扫描线，扫描 $r$，维护所有合法的 $l$。

先观察第一个条件，容易发现这限制了 $l$ 必须在某个区间内，太靠左最大值就会超过 $s_r$。设这个限制范围为 $[lim_r,r]$。

再考虑第二个条件，这个条件是关于 $l$ 的，一种处理方法是同样处理出这个区间，然后扫描的同时加入和删除对应的 $l$。但是这样不太方便解决第五个限制。

更机智的处理方法是，观察到合法的 $l$ 在扫到 $r$ 时，$s_{l-1}$ 一定是后缀最小值。 因此我们可以维护一个单调栈，存所有合法的 $l$，这样的好处是 $s_r-s_{l-1}\ge M$ 满足条件的就一定是单调栈上的一段前缀了（因为这时候 $s_{l-1}$ 越前越小，限制更松）。利用这个单调性，我们就可以在查询的时候，在单调栈上二分出有效的区间。

第三、四个条件只和 $l,r$ 中一个相关，只加入合法的点即可。

因此我们扫描线的过程大致如下：

• 计算所有以 $r$ 为右端点的合法区间：单调栈上二分，线段树查询；

• 弹出所有 $s_{l_0-1}>s_{r}$ 的 $l_0$，并将不合法的 $l_0$ 从线段树上删除；

• 加入 $l-1=r$ 这个决策，并在线段树上更新。

最后还需要支持多次查询，询问差分一下之后是个单点修改区间历史和，类似维护即可。

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

一份自认为实现的很帅的代码，供大家参考（如果不理解也可以看看代码，手模几步过程应该很快就会懂的）

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
const ll maxN=5e5+9;
ll tr[maxN<<2],his[maxN<<2],tag[maxN<<2],n,m,sumb[maxN],pre[maxN],suf[maxN],abst,lim[maxN];
void Pushdown(ll x){
    if(!tag[x])return ;
    his[x<<1]+=tr[x<<1]*tag[x];
    tag[x<<1]+=tag[x];
    his[x<<1|1]+=tr[x<<1|1]*tag[x];
    tag[x<<1|1]+=tag[x];
    tag[x]=0;
}
void Upd(ll x,ll l,ll r,ll u,ll v){
    if(l==r)return tr[x]+=v,void();
    ll mid=(l+r)>>1;
    Pushdown(x);
    if(u<=mid)Upd(x<<1,l,mid,u,v);
    else Upd(x<<1|1,mid+1,r,u,v);
    tr[x]=tr[x<<1]+tr[x<<1|1];
    his[x]=his[x<<1]+his[x<<1|1];
}
void Hist(ll x,ll l,ll r,ll ql,ll qr){
    if(ql<=l&&r<=qr)return his[x]+=tr[x],tag[x]++,void();
    ll mid=(l+r)>>1;
    Pushdown(x);
    if(ql<=mid)Hist(x<<1,l,mid,ql,qr);
    if(qr>mid)Hist(x<<1|1,mid+1,r,ql,qr);
    tr[x]=tr[x<<1]+tr[x<<1|1];
    his[x]=his[x<<1]+his[x<<1|1];
}
ll Query(ll x,ll l,ll r,ll ql,ll qr){
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return his[x];
    Pushdown(x);
    ll mid=(l+r)>>1;
    if(qr<=mid)return Query(x<<1,l,mid,ql,qr);
    if(ql>mid)return Query(x<<1|1,mid+1,r,ql,qr);
    return Query(x<<1,l,mid,ql,qr)+Query(x<<1|1,mid+1,r,ql,qr);
}
vector<array<ll,2> >vq[maxN];
ll stk[maxN],top;
std::vector<long long> maxsum(
    std::vector<int> A, std::vector<int> B, 
    std::vector<int> L1, std::vector<int> R1, 
    std::vector<int> L2, std::vector<int> R2){
    n=A.size(),m=L1.size();
    A.insert(A.begin(),0),B.insert(B.begin(),0);
    vector<ll>ans(m,0);
    for(int&x:L1)x++;
    for(int&x:L2)x++;
    for(int&x:R1)x++;
    for(int&x:R2)x++;
    rep(i,0,m-1){
        vq[L2[i]-1].push_back({-1,i});
        vq[R2[i]].push_back({1,i});
    }
    rep(i,1,n)sumb[i]=sumb[i-1]+B[i];
    rep(i,1,n)pre[i]=max(pre[i-1]+A[i],0ll);
    per(i,n,1)suf[i]=max(suf[i+1]+A[i],0ll);
    abst=-1e18;
    rep(i,1,n)abst=max(abst,pre[i-1]+A[i]);
    rep(i,1,n){
        while(top&&sumb[stk[top]]<=sumb[i])top--;
        lim[i]=stk[top],stk[++top]=i;
    }
    memset(stk,0,sizeof(stk));
    top=1,Upd(1,0,n,0,1);
    rep(r,1,n){
        ll ql=1,qr=top,ok=0;
        while(ql<=qr){
            ll mid=(ql+qr)>>1;
            if(sumb[r]-sumb[stk[mid]]>=abst)ok=mid,ql=mid+1;
            else qr=mid-1;
        }
        if(suf[r+1]==0&&ok)Hist(1,0,n,lim[r],stk[ok]);
        for(array<ll,2> qu:vq[r]){
            ll sgn=qu[0],id=qu[1];
            ll lf=L1[id]-1,rg=R1[id]-1;
            ans[id]+=sgn*Query(1,0,n,lf,rg);
        }
        while(top&&sumb[stk[top]]>sumb[r]){
            if(pre[stk[top]]==0)Upd(1,0,n,stk[top],-1);
            top--;
        }
        if(pre[r]==0)Upd(1,0,n,r,1);
        stk[++top]=r;
    }
    return ans;
}