#4212. 旅行规划（travel）

题意
OIVillage 是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl 决定修建了一条铁路将当地 $n$ 个最著名的经典连接起来，让游客可以通过火车从铁路起点（ $1$ 号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl 为每一个景区都赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。

xkszltl 希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而 xkszltl 的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl 无法及时完成任务，于是找到了准备虐杀 NOI2019 的你，希望你能帮助他完成这个艰巨的任务。
题解
考虑分块凸包
设 $s_i$ 表示 $i$ 的前缀和， $d_j$ 表示 $j$ 这个区间的每个数都加上它， $f_j$ 表示每位置的前缀和都加上它
对于第 $j$ 块的区间 $[l,r]$ 考虑它的 $ans$
$ans=max_{i=l}^{r} f_j+d_j imes (i-l)+s_i$
设 $x=i-l$ ， $y=s_i$ ，把式子化简成 $y=-d_j imes x+ans-f_j$ 故维护上凸壳即可

#include <bits/stdc++.h>
#define I inline
#define db double
#define LL long long
using namespace std;
const int N=1e5+5,M=350;
LL s[N],f[M],d[M],c[M];
int m,n,B,b[N],L[M],R[M],Z,S[M],p[M][M],sz[M];
I db K(int x,int y){return (db)(s[y]-s[x])/(db)(y-x);}
I void U(int x){
    int t=0;S[++t]=L[x];
    for (int i=L[x]+1;i<=R[x];i++){
        while(t>1 && K(S[t-1],S[t])<K(S[t-1],i))
            t--;
        S[++t]=i;
    }
    sz[x]=t;p[x][t+1]=n+1;
    for (int i=1;i<=t;i++) p[x][i]=S[i];
}
I void D(int x){
    LL t=f[x];
    for (int i=L[x];i<=R[x];i++)
        s[i]+=t+c[x],t+=d[x];
    f[x]=c[x]=d[x]=0;
}
I void C(int l,int r,LL k){
    int x=b[l],y=b[r];LL t=k*(L[x+1]-l+1);
    for (int i=x+1;i<y;i++)
        f[i]+=t,d[i]+=k,t+=k*(R[i]-L[i]+1);
    D(x);t=k;
    for (int i=l;i<=R[x] && i<=r;i++)
        s[i]+=t,t+=k;
    U(x);D(y);if (x!=y){
        t=k*(L[y]-l+1);
        for (int i=L[y];i<=r;i++)
            s[i]+=t,t+=k;
    }t=k*(r-l+1);
    for (int i=r+1;i<=R[y];i++) s[i]+=t;
    U(y);for (int i=y+1;i<=Z;i++) c[i]+=t;
}
I LL G(int x){
    if (!x || x>n) return (LL)-2e18;
    int y=b[x];return s[x]+c[y]+f[y]+d[y]*(x-L[y]);
}
I LL A(int x){
    int l=1,r=sz[x];
    while(l<=r){
        int mid=(l+r)>>1;
        LL t1=G(p[x][mid-1]);
        LL t2=G(p[x][mid]);
        LL t3=G(p[x][mid+1]);
        if (t1<t2 && t2<t3) l=mid+1;
        else if (t1>t2 && t2>t3) r=mid-1;
        else return t2;
    }
}
I LL Q(int l,int r){
    int x=b[l],y=b[r];LL t=-2e18;
    for (int i=x+1;i<y;i++)
        t=max(A(i),t);
    for (int i=l;i<=R[x] && i<=r;i++)
        t=max(G(i),t);if (x!=y)
    for (int i=L[y];i<=r;i++)
        t=max(G(i),t);return t;
}
int main(){
    scanf("%d",&n);B=sqrt(n);
    for (int x,i=1;i<=n;i++){
        scanf("%d",&x);
        s[i]=s[i-1]+x;
        b[i]=(i-1)/B+1;
        if (b[i]!=b[i-1])
            L[b[i]]=i,R[b[i-1]]=i-1;
    }R[Z=b[n]]=n;
    for (int i=1;i<=Z;i++) U(i);
    scanf("%d",&m);LL x;
    for (int op,l,r;m--;){
        scanf("%d%d%d",&op,&l,&r);
        if (!op) scanf("%lld",&x),C(l,r,x);
        else printf("%lld
",Q(l,r));
    }
    return 0;
}