P9877 [EC Final 2021] Vacation 题解

· · 题解

题目描述

给定序列 a_1,\dots,a_n 和常数 c，m 次询问，每次询问给出 l,r，询问所有满足 l\le l^\prime \le r^\prime\le r 且 r^\prime-l^\prime+1\le c 的 [l^\prime,r^\prime] 区间和的最大值。

思路

按照 c 分块，则合法的答案必然完全在一个块内或者是一个块的后缀和下一块的前缀拼接得来。

对于块内的问题，我们仅需使用线段树维护不加任何限制的最大子段和即可，由于块数可能很多，因此还要再使用另外一颗线段树维护区间内所有块内部的最大子段和的最大值。

对于块间的问题，预处理出当前块的后缀和 f 和下一块的前缀和 g，下标均从 1 开始。记当前块左端点为 S。若区间 [l^\prime,r^\prime] 是满足条件的，则要求 r^\prime-c\lt l^\prime，此时区间和可表示为 f_{l^\prime-S+1}+g_{r^\prime-c-S+1}，即对于 f_i 和 g_j，若 j<i，则 f_i+g_j 恰好对应一个合法区间的和。因此，对于每一块维护一颗线段树，线段树上维护该和最大值即可。同块内的问题一样，仍需另外一颗线段树维护区间内所有块与下一块拼接的最大值。

在查询时，先判掉 r-l+1\le c 的所有询问，这些询问仅需输出这个区间内的最大子段和。

对于 l,r 所在块不相邻的询问，中间所有块的贡献可以用上述两个维护最大值的线段树得到。两边的散块内部的贡献仅需查询对应区间的最大子段和。记左端点所在块的最左端为 L，右端点所在块的最左端 R。散块与相邻整块的拼接产生的贡献仅需在 l 所在块的线段树上查询区间 [l-L+1,c]，在 r 所在块左侧块的线段树上查询区间 [1,r-R+1] 即可包含所有情况。

对于 l,r 位于相邻两块的询问，仿照上一部分，在 l 所在块内的线段树上查询区间 [l-L+1,r-R+1]，但是这并未包含两散块拼接产生所有情况。具体的，漏了所有左端点 l^\prime 位于 (r-c,L+c-1] 中的区间，但是发现此时 l^\prime 到 r 的距离小于 c，仅需查询 [r-c+1,r] 内的最大子段和即可包括这部分贡献。同理，仅需查询 [l,l+c-1] 对应的最大子段和即可包括 r^\prime 在 [R,l+c) 内的所有区间的贡献。

总时间复杂度 O(n\log n)，但是常数巨大。

Code

constexpr int N=2e5+5;using ll=long long;constexpr ll inf=1e18;
#define lsc ro<<1
#define rsc ro<<1|1
#define now tree[ro]
struct sg1
{
    struct dat{ll lmx,rmx,sum,ans;inline dat()=default;inline dat(ll x):lmx(x),rmx(x),sum(x),ans(x){}};
    inline friend dat operator+(const dat&x,const dat&y)
    {
        dat res;res.sum=x.sum+y.sum;
        res.lmx=max(x.lmx,y.lmx+x.sum);
        res.rmx=max(y.rmx,x.rmx+y.sum);
        res.ans=max({x.ans,y.ans,x.rmx+y.lmx});
        return res;
    }
    struct node{int l,r;dat w;}tree[N<<2];
    inline void push_up(int ro){now.w=tree[lsc].w+tree[rsc].w;}
    inline void build(int ro,int l,int r,ll a[])
    {
        now.l=l,now.r=r;if(l==r) return now.w=dat(a[l]),void();
        int mid=(l+r)>>1;build(lsc,l,mid,a);build(rsc,mid+1,r,a);
        push_up(ro);
    }
    inline void update(int ro,int pos,ll x)
    {
        if(now.l==now.r) return now.w=dat(x),void();
        int mid=(now.l+now.r)>>1;
        if(pos<=mid) update(lsc,pos,x);
        else update(rsc,pos,x);
        push_up(ro);
    }
    inline dat query(int ro,int l,int r)
    {
        if(l==now.l&&now.r==r) return now.w;
        int mid=(now.l+now.r)>>1;
        if(r<=mid) return query(lsc,l,r);
        else if(l>mid) return query(rsc,l,r);
        else return query(lsc,l,mid)+query(rsc,mid+1,r);
    }
}t1;
struct sg2
{
    struct dat{ll lmx,rmx,ans;inline dat()=default;inline dat(ll x,ll y):lmx(x),rmx(y),ans(-inf){}};
    inline friend dat operator+(const dat&x,const dat&y)
    {
        dat res;res.lmx=max(x.lmx,y.lmx);res.rmx=max(x.rmx,y.rmx);
        res.ans=max({x.ans,y.ans,x.rmx+y.lmx});return res;
    }
    struct node{int l,r;dat w;ll t1,t2;};
    static node bt[N<<2],*nt;node*tree;
    inline void init(int n){tree=nt;nt+=n*4;}
    inline void push_up(int ro){now.w=tree[lsc].w+tree[rsc].w;}
    inline void push_tag(int ro,ll t1,ll t2)
    {
        now.w.lmx+=t1;now.w.ans+=t1+t2;
        now.w.rmx+=t2;now.t1+=t1;now.t2+=t2;
    }
    inline void push_down(int ro)
    {
        if(!now.t1&&!now.t2) return;
        push_tag(lsc,now.t1,now.t2);
        push_tag(rsc,now.t1,now.t2);
        now.t1=now.t2=0;
    }
    inline void build(int ro,int l,int r,ll a1[],ll a2[])
    {
        now.l=l,now.r=r;int mid=(now.l+now.r)>>1;
        if(l==r) return now.w=dat(a1[l],a2[l]),void();
        build(lsc,l,mid,a1,a2);build(rsc,mid+1,r,a1,a2);push_up(ro);
    }
    inline dat query(int ro,int l,int r)
    {
        if(now.l==l&&now.r==r) return now.w;
        int mid=(now.l+now.r)>>1;push_down(ro);
        if(r<=mid) return query(lsc,l,r);
        else if(l>mid) return query(rsc,l,r);
        else return query(lsc,l,mid)+query(rsc,mid+1,r);
    }
    inline void update(int ro,int l,int r,ll t1,ll t2)
    {
        if(l<=now.l&&now.r<=r) return push_tag(ro,t1,t2);
        int mid=(now.l+now.r)>>1;push_down(ro);
        if(l<=mid) update(lsc,l,r,t1,t2);
        if(r>mid) update(rsc,l,r,t1,t2);
        push_up(ro);
    }
}t2[N];sg2::node sg2::bt[N<<2],*sg2::nt=bt;
struct sg3
{
    struct node{int l,r;ll w;}tree[N<<2];
    inline void push_up(int ro){now.w=max(tree[lsc].w,tree[rsc].w);}
    inline void build(int ro,int l,int r)
    {
        now.l=l,now.r=r;if(l==r) return;
        int mid=(now.l+now.r)>>1;
        build(lsc,l,mid);build(rsc,mid+1,r);
    }
    inline void update(int ro,int pos,ll x)
    {
        if(now.l==now.r) return now.w=x,void();
        int mid=(now.l+now.r)>>1;
        if(pos<=mid) update(lsc,pos,x);
        else update(rsc,pos,x);
        push_up(ro);
    }
    inline ll query(int ro,int l,int r)
    {
        if(now.l==l&&now.r==r) return now.w;
        int mid=(now.l+now.r)>>1;
        if(r<=mid) return query(lsc,l,r);
        else if(l>mid) return query(rsc,l,r);
        else return max(query(lsc,l,mid),query(rsc,mid+1,r));
    }
}t3,t4;
ll a[N],p1[N],p2[N];int bel[N],L[N],R[N];
inline void work()
{
    using namespace IO;
    int n,m,B,btot;qread(n),qread(m),qread(B);btot=(n-1)/B+1;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/B+1,R[bel[i]]=i,qread(a[i]);
    for(int i=n;i;i--) L[bel[i]]=i; 
    t1.build(1,1,n,a);t3.build(1,1,btot);t4.build(1,1,btot);
    for(int i=1;i<=btot;i++)
    {
        t3.update(1,i,t1.query(1,L[i],R[i]).ans);
        if(i==btot) continue;
        t2[i].init(R[i]-L[i]+1);p2[L[i+1]-1]=0;
        for(int j=R[i];j>=L[i];j--) p1[j]=p1[j+1]+a[j];
        for(int j=L[i+1];j<=R[i+1];j++) p2[j]=p2[j-1]+a[j];
        t2[i].build(1,1,R[i]-L[i]+1,p1+L[i]-1,p2+L[i+1]-1);
        t4.update(1,i,t2[i].tree[1].w.ans);
    }
    while(m--)
    {
        int op,l,r;qread(op),qread(l),qread(r);
        if(op==1)
        {
            int bl=bel[l];ll dt=r-a[l];a[l]=r;t1.update(1,l,r);t3.update(1,bl,t1.query(1,L[bl],R[bl]).ans);
            if(bl!=btot) t2[bl].update(1,1,l-L[bl]+1,dt,0),t4.update(1,bl,t2[bl].tree[1].w.ans);
            if(bl!=1) t2[bl-1].update(1,l-L[bl]+1,R[bl-1]-L[bl-1]+1,0,dt),t4.update(1,bl-1,t2[bl-1].tree[1].w.ans);
        }
        else
        {
            ll ans=0;if(r-l+1<=B) ans=max(0ll,t1.query(1,l,r).ans);
            else
            {
                ans=max({ans,t1.query(1,l,l+B-1).ans,t1.query(1,r-B+1,r).ans});
                if(bel[l]+1==bel[r]) ans=max(ans,t2[bel[l]].query(1,l-L[bel[l]]+1,r-L[bel[r]]+1).ans);
                else
                {
                    ans=max({ans,t3.query(1,bel[l]+1,bel[r]-1),t2[bel[l]].query(1,l-L[bel[l]]+1,B).ans,t2[bel[r]-1].query(1,1,r-L[bel[r]]+1).ans});
                    if(bel[l]+2!=bel[r]) ans=max(ans,t4.query(1,bel[l]+1,bel[r]-2));
                }
            }
            qwrite(ans),pc('\n');
        }
    }
}