[BZOJ2388]旅行规划

Posted by Dispwnl on February 16, 2019

题目

Description

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

xkszltl希望为每位旅客提供最佳的旅行指导,但是由于游客的时间有限,不一定能游览全部景区,然而他们也不希望旅途过于短暂,所以每个游客都希望能在某一个区间内的车站结束旅程,而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了,xkszltl无法及时完成任务,于是找到了准备虐杀NOI2011的你,希望你能帮助他完成这个艰巨的任务。

Input

第一行给出一个整数n,接下来一行给出n的景区的初始美观度。

第三行给出一个整数m,接下来m行每行为一条指令:

  1. 0 x y k:表示将x到y这段铁路边上的景区的美观度加上k;

  2. 1 x y:表示有一名旅客想要在x到y这段(含x与y)中的某一站下车,你需要告诉他最大的旅行价值。

Output

对于每个询问,输出一个整数表示最大的旅行价值。

Sample Input

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

Sample Output

9
22

HINT

Data Limit:

对于20%的数据,n,m≤3000;

对于40%的数据,n,m≤30000;

对于50%的数据,n,m≤50000;

另外20%的数据,n,m≤100000,修改操作≤20;

对于100%的数据,n,m≤100000。

题解

题目要求的就是区间前缀和的最大值,区间$[l,r]$加$k$相当于区间$[l,r]$加一个首项、步长都为$k$的等差序列,区间$[r+1,n]$加一个首项为$(r-l+1)\times k$、步长为$0$的等差序列

这个东西用线段树无法维护,考虑分块,记录每一块的总的首项$b$和步长$d$,假设初始的前缀和序列为$S$,则若位置$j$比$i(j>i)$更优,有$i\times d+S_i+b$

移项化简后有$\frac{S_i-S_j}{j-i}<d​$

前面的东西就相当于一个斜率的相反数,所以每个块建出上凸壳然后在上面二分即可,零散块直接重构凸壳

蠢如我开始建了一个“凹壳”然后死活调不出来哪里错了……

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5;
struct Point{
	int x;
	LL y;
	Point(int X=0,LL Y=0) {x=X,y=Y;}
}st[MAX];
int n,m,k,N;
int a[MAX],bl[MAX],br[MAX],pos[MAX],T[MAX];
LL sum[MAX],Tk[MAX],Tb[MAX];
LL Cross(Point x,Point y) {return x.x*y.y-x.y*y.x;}
Point operator- (Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}
Point operator+ (Point x,Point y) {return Point(x.x+y.x,x.y+y.y);}
double Cal(Point x,Point y) {return double(y.y-x.y)/double(x.x-y.x);}
int read()
{
	int x=0,fl=1;
	char ch=getchar();
	for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x*fl;
}
void build(int x)
{
	int Top=bl[x];
	st[Top]=Point(1,sum[Top]);
	for(int i=bl[x]+1;i<=br[x];++i)
	  {
	  	while(Top>bl[x]&&Cross(st[Top]-st[Top-1],Point(i-bl[x]+1,sum[i])-st[Top])>0) --Top;
	  	st[++Top]=Point(i-bl[x]+1,sum[i]);
	  }
	T[x]=Top;
}
void change(int l,int r,int k,int b=0)
{
	if(l>n) return;
	int Pl=pos[l],Pr=pos[r];
	if(Pl==Pr)
	{
		if(l==bl[Pl]&&r==br[Pr])
		{
			Tb[Pl]+=b;
			return void(Tk[Pl]+=k);
		}
		for(int i=l;i<=r;++i)
		  sum[i]+=1ll*(i-l+1)*k+b;
		return void(build(Pl));
	}
	int L=Pl+(bl[Pl]!=l),R=Pr-(br[Pr]!=r);
	for(int i=L;i<=R;++i)
	  Tk[i]+=k,Tb[i]+=1ll*(bl[i]-l)*k+b;
	if(L!=Pl)
	{
		for(int i=l;i<=br[Pl];++i)
		  sum[i]+=1ll*(i-l+1)*k+b;
		build(Pl);
	}
	if(R!=Pr)
	{
		for(int i=bl[Pr];i<=r;++i)
		  sum[i]+=1ll*(i-l+1)*k+b;
		build(Pr);
	}
}
LL ask(int x)
{
	int l=bl[x]+1,r=T[x],ans=bl[x];
	while(l<=r)
	{
		int mid(l+r>>1);
		if(st[mid-1].y-st[mid].y<1ll*(st[mid].x-st[mid-1].x)*Tk[x]) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return 1ll*st[ans].x*Tk[x]+st[ans].y+Tb[x];
}
LL ask(int l,int r)
{
	LL ans=-1e18;
	int Pl=pos[l],Pr=pos[r];
	if(Pl==Pr)
	{
		if(l==bl[Pl]&&r==br[Pr]) return ask(Pl);
		for(int i=l;i<=r;++i)
		  ans=max(ans,1ll*(i-bl[Pl]+1)*Tk[Pl]+sum[i]+Tb[Pl]);
		return ans;
	}
	int L=Pl+(bl[Pl]!=l),R=Pr-(br[Pr]!=r);
	for(int i=L;i<=R;++i)
	  ans=max(ans,ask(i));
	if(L!=Pl) for(int i=l;i<=br[Pl];++i)
	  ans=max(ans,1ll*(i-bl[Pl]+1)*Tk[Pl]+sum[i]+Tb[Pl]);
	if(R!=Pr) for(int i=bl[Pr];i<=r;++i)
	  ans=max(ans,1ll*(i-bl[Pr]+1)*Tk[Pr]+sum[i]+Tb[Pr]);
	return ans;
}
int main()
{
	k=sqrt(n=read()),N=(n-1)/k+1;
	for(int i=1,x;i<=n;++i)
	  {
	  	a[i]=read(),sum[i]=sum[i-1]+a[i],pos[i]=x=(i-1)/k+1,br[x]=i;
	  	if(!bl[x]) bl[x]=i;
	  }
	for(int i=1;i<=N;++i)
	  build(i);
	m=read();
	for(int i=1,op,x,y,K;i<=1;++i)
	  {
	  	op=read(),x=read(),y=read();
	  	if(!op) change(x,y,K=read()),change(y+1,n,0,1ll*(y-x+1)*K);
	  	else printf("%lld\n",ask(x,y));
	  }
	return 0;
}