题解：P11947 [KTSC 2025] 可爱区间 / maxsum

· · 题解

一个很简洁的做法。

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

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

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

考虑扫描线，扫描 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 中一个相关，只加入合法的点即可。

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

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

时间复杂度 \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;
}