P9877 [EC Final 2021] Vacation 题解

· · 题解

P9877 [EC Final 2021] Vacation 题解

题目大意：给定常数 C，若干次询问一个区间内长度为 [0,C] 的子段和的最大值，支持单点修改。

考虑把序列每 C 个分一块，分成 \lceil\frac nc\rceil 块。那么发现符合条件的子段只可能在一个块内或相邻两个块内。

在一个块内的情况

那么问题转化为了求区间的最大子段和，这个问题是经典的，即 GSS3。这里复述一遍做法：

那么对每个块开一棵维护最大子段和的线段树，然后再对全局开一棵线段树维护每个块的最大子段和的最大值用于区间查询。

在相邻两个块的情况

考虑一个符合条件的区间满足什么条件，对于 l\le kC<r，要满足 r-l+1\le C 即 r-C<l。

设 a_i 为 l=i 时 l 所在块中以 l 开始的后缀和，b_i 为 r=i+C 时 r 所在块中以 r 结束的前缀和。那么这两个相邻区间的贡献就是满足 j<i 的 a_i+b_j 的最大值。

那么对每相邻两个块开一棵线段树，每个节点分别维护区间内 a,b 的最大值，同时维护上述 i,j 都在区间内时的答案 ans，那么合并区间时，ans_x=\max(ans_{lson},ans_{rson},b_{lson}+a_{rson})。

然后由于单点修改时会导致块内一个区间的前缀和或后缀和改变，所以我们还要维护一个区间加标记，用正常方式下传即可，当区间的 a 或 b 加 x 时，ans 也要加 x（前提是区间长度大于 1）。

同时如上一节，需要对全局开一个线段树维护每相邻两个块的答案的最大值，以便于区间查询。

对于散块的情况

对于整块的情况直接在我们开的全局的线段树上查询即可。现在考虑散块的情况。

询问的 l,r 在同一个块内的情况：

此时直接查询区间最大子段和。

询问的 l,r 之间间隔至少一个块的情况：

此时除了整块的贡献，还有以下贡献：

对于两个散块内的贡献，直接查询区间最大子段和。

对于散块与整块之间的贡献，我们以左边的散块为例。我们设造成贡献的区间为左右端点为 i,j，询问的左端点为 l，这里的 i,j,l 为对应在块中的编号，它们的取值都为 [1,C]。

贡献有两种，分别为 l\le j<i\le C 与 1\le j<l\land l\le i\le C，前者直接查询区间内的答案，后者分别查询区间内 b 与 a 的最大值即可。

询问的 l,r 在相邻两个块的情况：

如果不跨过块，依旧是分别查询区间最大子段和。

考虑跨过块：这里 l,r 依然代表在对应块中的编号。

时间复杂度与常数

最多使用了区间加懒标记的线段树，时间复杂度 O(m\log n)，对于每一个块的线段树可以考虑使用 vector 开空间。

常数方面，对于我的代码，修改最多调用 6 次函数，查询一个块最多 1 次，查询相邻块最多 7 次，查询相隔至少一个块最多 8 次。

可以稳过，对于加强版也可以通过。

其他细节

这里对于不满 C 的块我补满了 C，因此数组大小最大是 2n 的。

代码实现

评测记录一，评测记录二。

struct arr1 {
    ll ans,maxa,maxb;
    arr1 operator+(arr1 x) {
        return {
            max(max(ans,x.ans),maxb+x.maxa),
            max(maxa,x.maxa),
            max(maxb,x.maxb),
        };
    }
};
struct arr2 {
    ll ans,pre,suf,sum;
    arr2 operator+(arr2 x) {
        return {
            max(max(ans,x.ans),suf+x.pre),
            max(pre,sum+x.pre),
            max(suf+x.sum,x.suf),
            sum+x.sum
        };
    }
};
struct tree1 {
    vector<arr1> s;
    vector<ll> ta,tb;
    void resize() {
        s.resize(C*4+5);
        ta.resize(C*4+5);
        tb.resize(C*4+5);
    }
    void make(int x,int l,int r,ll *a,ll *b) {
        if(l==r) {
            s[x].maxa=a[C]-a[l-1];
            s[x].maxb=b[l]-b[0];
            s[x].ans=-9e18;
            return;
        }
        make(ls,l,mid,a,b),make(rs,mid+1,r,a,b);
        s[x]=s[ls]+s[rs];
    }
    void pushdown(int x,int l,int r) {
        if(ta[x]) {
            s[x].maxa+=ta[x];
            if(l<r) s[x].ans+=ta[x],ta[ls]+=ta[x],ta[rs]+=ta[x];
            ta[x]=0;
        }
        if(tb[x]) {
            s[x].maxb+=tb[x];
            if(l<r) s[x].ans+=tb[x],tb[ls]+=tb[x],tb[rs]+=tb[x];
            tb[x]=0;
        }
    }
    void add(int x,int l,int r,int L,int R,int opt,int y) {
        if(L<=l&&r<=R) {
            if(opt==0) ta[x]+=y;
            else tb[x]+=y;
            pushdown(x,l,r);
            return;
        }
        pushdown(x,l,r);
        if(R<l||r<L) return;
        add(ls,l,mid,L,R,opt,y),add(rs,mid+1,r,L,R,opt,y);
        s[x]=s[ls]+s[rs];
    }
    arr1 query(int x,int l,int r,int L,int R) {
        pushdown(x,l,r);
        if(L<=l&&r<=R) return s[x];
        if(L<=mid&&R>mid) return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
        if(L<=mid) return query(ls,l,mid,L,R);
        return query(rs,mid+1,r,L,R);
    }
}tr1[N];
struct tree2 {
    vector<arr2> s;
    void resize() {
        s.resize(C*4+5);
    }
    void make(int x,int l,int r,int *a) {
        if(l==r) {
            s[x].ans=s[x].pre=s[x].suf=s[x].sum=a[l];
            return;
        }
        make(ls,l,mid,a),make(rs,mid+1,r,a);
        s[x]=s[ls]+s[rs];
    }
    void update(int x,int l,int r,int y,int z) {
        if(l==r) {
            s[x].ans=s[x].pre=s[x].suf=s[x].sum=z;
            return;
        }
        if(y<=mid) update(ls,l,mid,y,z);
        else update(rs,mid+1,r,y,z);
        s[x]=s[ls]+s[rs];
    }
    arr2 query(int x,int l,int r,int L,int R) {
        if(L<=l&&r<=R) return s[x];
        if(L<=mid&&R>mid) return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
        if(L<=mid) return query(ls,l,mid,L,R);
        return query(rs,mid+1,r,L,R);
    }
}tr2[N];
struct tree3 {
    ll s[N*4];
    void update(int x,int l,int r,int y,ll z) {
        if(l==r) {
            s[x]=z;
            return;
        }
        if(y<=mid) update(ls,l,mid,y,z);
        else update(rs,mid+1,r,y,z);
        s[x]=max(s[ls],s[rs]);
    }
    ll query(int x,int l,int r,int L,int R) {
        if(L<=l&&r<=R) return s[x];
        if(R<l||r<L) return 0;
        return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
    }   
}tr3,tr4;
int n,m,a[N];
ll pre[N];
signed main(){
    read(n,m,C);
    fo(i,1,n) read(a[i]),pre[i]=pre[i-1]+a[i];
    fo(i,0,bn(n)-1) {
        tr1[i].resize();
        tr1[i].make(1,1,C,pre+i*C,pre+i*C+C);
        tr3.update(1,0,bn(n),i,tr1[i].s[1].ans);
    }
    fo(i,0,bn(n)) {
        tr2[i].resize(), tr2[i].make(1,1,C,a+i*C);
        tr4.update(1,0,bn(n),i,tr2[i].s[1].ans);
    }
    while(m--) {
        int opt; read(opt);
        if(opt==1) {
            int x,y; read(x,y);
            tr2[bn(x)].update(1,1,C,x-bn(x)*C,y);
            tr4.update(1,0,bn(n),bn(x),tr2[bn(x)].s[1].ans);
            if(bn(x)>0) 
                tr1[bn(x)-1].add(1,1,C,x-bn(x)*C,C,1,y-a[x]),
                tr3.update(1,0,bn(n),bn(x)-1,tr1[bn(x)-1].s[1].ans);
            if(bn(x)<bn(n))
                tr1[bn(x)].add(1,1,C,1,x-bn(x)*C,0,y-a[x]),
                tr3.update(1,0,bn(n),bn(x),tr1[bn(x)].s[1].ans);
            a[x]=y;
            continue;   
        }
        ll ans=0;
        int l,r; read(l,r);
        int x=l-bn(l)*C,y=C;
        int u=1,v=r-bn(r)*C;
        if(bn(l)+1<bn(r)) {
            if(bn(l)+2<bn(r)) ans=max(ans,tr3.query(1,0,bn(n),bn(l)+1,bn(r)-2));
            ans=max(ans,tr4.query(1,0,bn(n),bn(l)+1,bn(r)-1));
            ans=max(ans,tr2[bn(l)].query(1,1,C,x,y).ans);
            ans=max(ans,tr2[bn(r)].query(1,1,C,u,v).ans);
            arr1 L=tr1[bn(l)].query(1,1,C,x,y);
            arr1 R=tr1[bn(r)-1].query(1,1,C,u,v);
            if(x!=1) ans=max(ans,tr1[bn(l)].query(1,1,C,1,x-1).maxb+L.maxa);
            if(v!=C) ans=max(ans,R.maxb+tr1[bn(r)-1].query(1,1,C,v+1,C).maxa);
            ans=max(ans,max(L.ans,R.ans));
        }
        else if(bn(l)==bn(r)) {
            ans=tr2[bn(l)].query(1,1,C,x,v).ans;
        }
        else {
            ans=max(ans,tr2[bn(l)].query(1,1,C,x,y).ans);
            ans=max(ans,tr2[bn(r)].query(1,1,C,u,v).ans);
            arr1 L=tr1[bn(l)].query(1,1,C,x,y),R=tr1[bn(l)].query(1,1,C,u,v);
            if(v<x) ans=max(ans,R.maxb+L.maxa);
            else {
                if(u<x) ans=max(ans,tr1[bn(l)].query(1,1,C,u,x-1).maxb+L.maxa);
                if(v<y) ans=max(ans,R.maxb+tr1[bn(l)].query(1,1,C,v+1,y).maxa);
                ans=max(ans,tr1[bn(l)].query(1,1,C,x,v).ans);
            }
        }
        write(max(0ll,ans),'\n');
    }
    return 0;
}