$spoj\ UNTITLE1$

题目大意

维护序列$\{a\}$, $|a_i|\leq 10^4$; 记$s_i=\sum_{j=1}^i a_j$

有两种操作

$0\ x\ y\ k$: 将$a_i$增加$k\ (x\leq i\leq y,\ |k|\leq 10^4)$

$1\ x\ y$: 询问$max(s_i\ |\ x\leq i\leq y)$

解

定义: $f(x)$表示$x$所在的块的序号

各种题解都是对$\{s\}$分块呐（据说可持久化平衡树也可以，然而我找不到$clj$的课件$orz$）

修改:

$$ s_i\rightarrow \left\{ \begin{array}{ll} s_i+k(i-x+1)=s_i+ki+k(1-x) & \textrm{$x\leq i\leq y$} \\ s_i+k(y-x+1) & \textrm{$y< i$} \end{array} \right. $$

$k(1-x),\ k(y-x+1)$为常数

对整块修改时, 所修改的常数是相等的, 用$\{c\}$记录; 用$\{k\}$记录每块共同增加的$k$

则询问时输出$max(s_i+k_{f(i)}i+c_{f(i)}\ |\ x\leq i\leq y)$

$\therefore k,\ c$是常数, 这个式子和斜率优化$dp$的状态转移方程类似

$\therefore$每次暴力修改后维护块中由所有$(i,s_i)$所构成的点集的上凸形; 每次对整块的询问, 对上凸形二分答案即可

Code

$ps$: $[0,n),\ [0,tot],\ [ql,qr),\ [l,r),\ [bl,br],\ rep(i,x,y)\Leftrightarrow For\ i\in[x,y)$

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
#define rep(i,x,y) for (int i=x; i<y; ++i)

using namespace std;
typedef long long ll;

int n,m,op,ql,qr,v,tot,st[225][225],sz,bl,br;
ll k[225],c[225],s[50000],ans;

inline int get()
{
    char ch;
    int ret;
    bool f;
    while (!isdigit(ch=getchar()) && ch!=45);
    for (ch==45? (ret=0,f=1):(ret=ch-48,f=0); isdigit(ch=getchar()); ret=ret*10+ch-48);
    return f? -ret:ret;
}

inline ll query(int x,int l=0,int r=0)
{
    if (l%sz || r%sz)
    {
        ll ret=s[l]+l*k[x];
        rep(i,l+1,r)
            ret=max(ret,s[i]+i*k[x]);
        return ret+c[x];
    }
    int *a=st[x],mid,t,t_;
    if (!*a)
        rep(i,x*sz,(x+1)*sz)
        {
            while (t=a[*a],t_=a[*a-1],*a>1 && (s[i]-s[t])*(t-t_)>(s[t]-s[t_])*(i-t))
                --*a;
            a[++*a]=i;
        }
    for (l=1,r=*a-1; l<=r;)
    {
        mid=l+r>>1,t=a[mid+1],t_=a[mid];
        if (s[t]-s[t_]>-k[x]*(t-t_))
            l=mid+1;
        else
            r=mid-1;
    }
    return s[a[l]]+a[l]*k[x]+c[x];
}

inline void modify(int x,int l=0,int r=0)
{
    if (l%sz || r%sz)
    {
        *st[x]=0;
        for (ll i=l,j=(l-ql+1)*v; i<r; ++i,j+=v)
            s[i]+=j;
        return;
    }
    k[x]+=v,c[x]+=(1-ql)*v;
}

int main()
{
    n=get(),sz=sqrt(n),tot=(n-1)/sz,s[0]=get();
    rep(i,1,n)
        s[i]=get()+s[i-1];
    for (int q=get(); q--;)
    {
        op=get(),ql=get()-1,qr=get(),bl=ql/sz,br=(qr-1)/sz;
        if (op)
        {
            if (bl==br)
                ans=query(bl,ql,qr);
            else
                ans=max(query(bl,ql,(bl+1)*sz),query(br,br*sz,qr));
            rep(i,bl+1,br)
                ans=max(ans,query(i));
            printf("%lld\n",ans);
        }
        else
        {
            if (v=get(),bl==br)
                modify(bl,ql,qr);
            else
                modify(bl,ql,(bl+1)*sz),modify(br,br*sz,qr);
            rep(i,bl+1,br)
                modify(i);
            v*=qr-ql;
            rep(i,qr,min(n,(br+1)*sz))
                s[i]+=v;
            rep(i,br+1,tot+1)
                c[i]+=v;
        }
    }
    return 0;
}