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

一个很简洁的做法。

先思考如何判断一个区间

[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)

。

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

CPP

#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;
}

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

文章操作

相关推荐

评论

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