自动搬运

查看原文

来自洛谷，原作者为

	hzoi_liuchang AFO

搬运于2025-08-24 21:57:31，当前版本为作者最后更新于2021-01-04 13:59:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

转化一下题意

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

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

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

考虑万能的分块做法

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

所以对每一个块维护等差数列的首项 $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;
}