题目
解法
考虑一次操作 \((0,x,y,k)\) 对前缀和 \(s_i\) 的影响：
\[\Delta =\begin{cases} k\cdot(i-x+1), & x\le i\le y \\k\cdot (y-x+1), & i>y\end{cases} \]先给每个下标设定一个 \(c_i\) 表示增加的定值，\(k_i\) 表示增加的 \(i\) 的系数。
那么询问 \((x,y)\) 的答案就是：
\[\text{Ans}=\max_{i=x}^y\{s_i+c_i+k_i\cdot i\} \]显然是过不去的。不过事实上可以将区间分块。
- \(s_i\) 还是表示 \(i\) 下标，处理非整块的情况。
- \(c_i,k_i\) 都表示第 \(i\) 个块的值。
问题转化为在长度为 \(B\) 的块内查找上文的 \(\max\)。
将下标 \(i\) 抽象成点 \((i,s_i)\)，那么 \(\text{Ans}\) 相当于斜率为 \(-k_{bl_i}\) 的过点 \(i,i\in S_{bl_i}\) 的最大截距。维护一个凸包，然后在凸包上二分斜率即可。当凸包被散块修改时，暴力重构凸包。
接下来计算一下复杂度：
- 修改。\(\mathcal O(m\cdot (B+\frac{n}{B}))\)。
- 查询。处理散块是 \(\mathcal O(mB)\) 的；对于整块，暴力重构单次是 \(\mathcal O(B)\) 的，总共是 \(\mathcal O(mB)\) 的，二分是 \(\mathcal O(m\cdot \frac{n}{B}\cdot \log\sqrt B)\) 的。
所以最优块长应该满足 \(\frac{B^2}{\log \sqrt B}=n\)（但是我没算常数），可能比 \(\sqrt n\) 略大，我直接取了 \(\sqrt n\)。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=5e4+500,maxb=230;
int n,m,B,bl[maxn],K,x,y;
int st[maxb][maxb];
ll s[maxn],k[maxn],c[maxn];
void modify(int pos,int l=0,int r=0) {
if(l and r) {
st[pos][0]=0;
ll tmp=1ll*K*(l-x+1);
for(int i=l;i<=r;++i)
s[i]+=tmp,tmp+=K;
}
else k[pos]+=K,c[pos]+=1ll*K*(1-x);
}
ll query(int pos,int l=0,int r=0) {
if(l and r) {
ll tmp=s[l]+k[pos]*l;
for(int i=l+1;i<=r;++i)
tmp=max(tmp,s[i]+k[pos]*i);
return tmp+c[pos];
}
if(!st[pos][0]) {
int *tp=&st[pos][0];
for(int i=(pos-1)*B+1;i<=pos*B;++i) {
while((*tp)>1 and 1ll*(s[i]-s[st[pos][*tp]])*(st[pos][*tp]-st[pos][*tp-1])>1ll*(s[st[pos][*tp]]-s[st[pos][*tp-1]])*(i-st[pos][*tp]))
--(*tp);
st[pos][++(*tp)]=i;
}
}
l=1,r=st[pos][0]-1; int mid,a,b;
while(l<=r) {
mid=l+r>>1;
a=st[pos][mid];
b=st[pos][mid+1];
if(s[b]-s[a]>-k[pos]*(b-a))
l=mid+1;
else r=mid-1;
}
return s[st[pos][l]]+c[pos]+k[pos]*st[pos][l];
}
signed main() {
n=read(9); B=sqrt(n);
for(int i=1;i<=n;++i)
s[i]=s[i-1]+read(9),
bl[i]=(i-1)/B+1;
m=read(9);
int op; ll ans;
while(m--) {
op=read(9),x=read(9);
y=read(9);
if(!op) {
K=read(9);
if(bl[x]^bl[y]) {
modify(bl[x],x,bl[x]*B);
modify(bl[y],(bl[y]-1)*B+1,y);
for(int i=bl[x]+1;i<bl[y];++i)
modify(i);
}
else modify(bl[x],x,y);
K*=(y-x+1);
for(int i=y+1;i<=bl[y]*B;++i)
s[i]+=K;
for(int i=bl[y]+1;i<=bl[n];++i)
c[i]+=K;
}
else {
ans=0;
if(bl[x]^bl[y]) {
ans=query(bl[x],x,bl[x]*B);
ans=max(ans,query(bl[y],(bl[y]-1)*B+1,y));
for(int i=bl[x]+1;i<bl[y];++i)
ans=max(ans,query(i));
}
else ans=query(bl[x],x,y);
print(ans,'\n');
}
}
return 0;
}