题解 P4192 【旅行规划】

· · 题解

分析

转化一下题意

区间加等差数列，查询区间最大值

如果是单点查询的话，可以在线段树上打一个标记，边查询边下放

但是区间查询的话需要整棵树下放标记，复杂度太高

考虑万能的分块做法

因为等差数列加等差数列还是还是一个等差数列

所以对每一个块维护等差数列的首项 beg 以及公差 d

这样，一个块内所有点的值都可以写成与下标相关的一次函数的形式

即 ans[i]=i \times d+sum[i]

sum[i]=ans[i]-i \times d

其中 sum[i] 为上一次重构后 i 处前缀和的值

对于整个块的首项，我们先不去考虑，最后把它加上即可

这样，我们就可以把下标 i 看成横坐标，把 sum[i] 看成纵坐标，把 -d 看成斜率

如果是对整个块进行修改，那么横纵坐标都是不变的

变化的只是斜率

因此可以维护一个上凸壳

在上凸壳中二分查找使截距 ans[i] 最大的点

如果是对块的一部分进行修改或查询，我们就把这个块进行暴力重构，重新建一个凸包

如果块长是 \sqrt{n} 的话

复杂度就是 m\sqrt{n}log\sqrt{n}

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
    rg int x=0,fh=1;
    rg char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*fh;
}
const int maxn=1e5+5;
typedef double db;
const db eps=1e-18;
struct Node{
    int x;
    long long y;
    Node(){}
    Node(rg int aa,rg long long bb){
        x=aa,y=bb;
    }
    friend bool operator < (const Node& A,const Node& B){
        if(A.x==B.x) return A.y<B.y;
        else return A.x<B.x;
    }
};
int shuyu[maxn],blo,n,m,l[maxn],r[maxn],tp,tail;
std::vector<Node> ans[maxn];
Node sta[maxn],que[maxn];
long long beg[maxn],sum[maxn],d[maxn];
inline double xl(rg Node aa,rg Node bb){
    if(std::fabs((double)bb.x-(double)aa.x)<eps){
        if(std::fabs((double)bb.y-(double)aa.y)<eps) return 0;
        else if(bb.y>aa.y) return 1e18;
        else return -1e18;
    }
    return ((double)bb.y-(double)aa.y)/((double)bb.x-(double)aa.x);
}
void build(rg int id){
    if(d[id]){
        for(rg int i=l[id];i<=r[id];i++) sum[i]+=1LL*d[id]*(i-l[id]+1);
        d[id]=0;
    }
    if(beg[id]){
        for(rg int i=l[id];i<=r[id];i++) sum[i]+=beg[id];
        beg[id]=0;
    }
    tp=tail=0;
    ans[id].clear();
    for(rg int i=l[id];i<=r[id];i++) sta[++tp]=Node(i-l[id]+1,sum[i]);
    std::sort(sta+1,sta+tp+1);
    for(rg int i=1;i<=tp;i++){
        while(tail>1 && xl(que[tail],sta[i])>=xl(que[tail-1],que[tail])) tail--;
        que[++tail]=sta[i];
    }
    for(rg int i=1;i<=tail;i++) ans[id].push_back(que[i]);
}
void xg(rg int nl,rg int nr,rg int val){
    for(rg int i=nl;i<=std::min(r[shuyu[nl]],nr);i++){
        sum[i]+=1LL*val*(i-nl+1);   
    }
    for(rg int i=nr+1;i<=r[shuyu[nr]];i++){
        sum[i]+=1LL*val*(nr-nl+1);
    }
    for(rg int i=shuyu[nr]+1;i<=shuyu[n];i++){
        beg[i]+=1LL*val*(nr-nl+1);
    }
    build(shuyu[nl]);
    if(shuyu[nl]==shuyu[nr]) return;
    for(rg int i=l[shuyu[nr]];i<=nr;i++){
        sum[i]+=1LL*val*(i-nl+1);
    }
    build(shuyu[nr]);
    for(rg int i=shuyu[nl]+1;i<=shuyu[nr]-1;i++){
        beg[i]+=1LL*(l[i]-nl)*val;
        d[i]+=val;
    }
}
long long qjcx(rg int id){
    rg int nl=1,nr=ans[id].size(),mids;
    rg double nans=-1.0*d[id];
    while(nl<nr){
        mids=(nl+nr)>>1;
        if(xl(ans[id][mids-1],ans[id][mids])<=nans) nr=mids;
        else nl=mids+1;
    }
    nl--;
    return (long long)ans[id][nl].y+(long long)d[id]*ans[id][nl].x+(long long)beg[id];
}
long long cx(rg int nl,rg int nr){
    build(shuyu[nl]);
    rg long long nans=-0x3f3f3f3f3f3f3f3f;
    for(rg int i=nl;i<=std::min(r[shuyu[nl]],nr);i++) nans=std::max(nans,sum[i]);
    if(shuyu[nl]==shuyu[nr]) return nans;
    build(shuyu[nr]);
    for(rg int i=l[shuyu[nr]];i<=nr;i++) nans=std::max(nans,sum[i]);
    for(rg int i=shuyu[nl]+1;i<=shuyu[nr]-1;i++){
        nans=std::max(nans,qjcx(i));
    }
    return nans;
}
int main(){
    memset(l,0x3f,sizeof(l));
    n=read();
    blo=sqrt(n);
    for(rg int i=1;i<=n;i++) shuyu[i]=(i-1)/blo+1;
    for(rg int i=1;i<=n;i++) sum[i]=read();
    for(rg int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(rg int i=1;i<=n;i++){
        l[shuyu[i]]=std::min(l[shuyu[i]],i);
        r[shuyu[i]]=std::max(r[shuyu[i]],i);
    }
    for(rg int i=1;i<=shuyu[n];i++) build(i);
    m=read();
    rg int aa,bb,cc,dd;
    for(rg int i=1;i<=m;i++){
        aa=read(),bb=read(),cc=read();
        if(aa==0){
            dd=read();
            xg(bb,cc,dd);
        } else {
            printf("%lld\n",cx(bb,cc));
        }
    }
    return 0;
}