思路和代码来源于 @ClCN

#include<cstdio>
#include<cstring>
#include<algorithm>
const long long Inf=0x3f3f3f3f3f3f3f3f;
struct Point
{
	long long x,y;
	Point(long long x=0,long long y=0):x(x),y(y){}
	inline friend Point operator+(const Point& a,const Point& b){return Point(a.x+b.x,a.y+b.y);}
	inline friend Point operator-(const Point& a,const Point& b){return Point(a.x-b.x,a.y-b.y);}
	inline friend long long Cross(const Point& a,const Point& b){return a.x*b.y-a.y*b.x;}
};
Point pool[20010000];
int pooltop;
Point* Allocate(int size)
{
	int tmp=pooltop;
	pooltop+=size;
	return pool+pooltop;
}
long long tag;
struct Hull
{
	Hull(){best=0;}
	Point* Data;
	int best,size;
	inline Point operator[](const int& x){return Data[x];}
	inline void Insert(const Point& x){Data[x.x].y=std::max(Data[x.x].y,x.y);}
	inline void PushBack(const Point& x){Data[size++]=x;}
	inline void Clean(const int& cnt)
	{
		Data[0]=Point(0,0);
		for(register int i=1;i<=cnt;i++)Data[i]=Point(i,-Inf);
		size=cnt+1;
	}
	inline void Convex()
	{
		if(size<=2)return;
		register int top=1;
		for(register int i=2;i<size;i++)
		{
			if(Data[i].y==-Inf)continue;
			while(top&&Cross(Data[top]-Data[top-1],Data[i]-Data[top-1])>=0)top--;
			Data[++top]=Data[i];
		}
		size=top+1;
	}
	inline long long MaxVal()
	{
		while(best+1<size&&(Data[best+1].x-Data[best].x)*tag+Data[best+1].y-Data[best].y>0)best++;
		return Data[best].x*tag+Data[best].y;
	}
	inline friend void Merge(Hull& c,Hull& a,Hull& b)
	{
		register int i=0,j=0,sizea=a.size,sizeb=b.size;
		c.Insert(a[i]+b[j]);
		while(i+1<sizea&&j+1<sizeb)
		{
			if(Cross(a[i+1]-a[i],b[j+1]-b[j])>=0)
				j++,c.Insert(a[i]+b[j]);
			else
				j++,c.Insert(a[i]+b[j]);
		}
		while(i+1<sizea)i++,c.Insert(a[i]+b[j]);
		while(j+1<sizeb)j++,c.Insert(a[i]+b[j]);
	}
};
struct Result
{
	long long data[2],ans,sum;
	Result(long long data1=0,long long data2=0,long long ans=0,long long sum=0)
		:ans(ans),sum(sum){data[0]=data1;data[1]=data2;}
	inline friend Result Merge(const Result& a,const Result& b)
		{return Result(std::max(a.data[0],a.sum+b.data[0]),std::max(b.data[1],b.sum+a.data[1]),std::max(std::max(a.ans,b.ans),a.data[1]+b.data[0]),a.sum+b.sum);}
};
long long Arr[310000];
const int MaxCnt=310000;
/*
       O
     /  \
    O   O
    
*/
struct Segment_Tree
{
	Segment_Tree(){Clean();}
	int cnt;
	int Son[MaxCnt<<2][2],Left[MaxCnt<<2],Right[MaxCnt<<2];
	Hull Data[MaxCnt<<2][2],Ans[MaxCnt<<2];
	long long Sum[MaxCnt<<1];
	inline void Clean(){cnt=0;}
	inline void MergeLeftRight(Hull& c,Hull& a,Hull& b,Point addtag)
	{
		register int sizea=a.size,sizeb=b.size;
		for(register int i=0;i<sizea;i++)c.PushBack(a[i]);
		for(register int i=0;i<sizeb;i++)c.PushBack(b[i]+addtag);
		c.Convex();
	}
	inline void PushUp(int now)
	{
		Ans[now].Clean(Right[now]-Left[now]+1);
		register int size;
		size=Ans[Son[now][0]].size;
		for(int i=0;i<size;i++)Ans[now].Insert(Ans[Son[now][0]][i]);
		size=Ans[Son[now][1]].size;
		for(int i=0;i<size;i++)Ans[now].Insert(Ans[Son[now][1]][i]);
		Merge(Ans[now],Data[Son[now][0]][1],Data[Son[now][1]][0]);
		Ans[now].Convex();
		Sum[now]=Sum[Son[now][0]]+Sum[Son[now][1]];
	}
	inline void Build(int &now,int left,int right)
	{
		now=++cnt;
		Left[now]=left;Right[now]=right;
		Data[now][0].Data=Allocate(right-left+3);
		Data[now][1].Data=Allocate(right-left+3);
		Ans[now].Data=Allocate(right-left+3);
		if(left==right)
		{
			Data[now][0].PushBack(Point(0,0));
			Data[now][0].PushBack(Point(1,Arr[left]));
			Data[now][1].PushBack(Point(0,0));
			Data[now][1].PushBack(Point(1,Arr[left]));
			Ans[now].PushBack(Point(0,0));
			Ans[now].PushBack(Point(1,Arr[left]));
			Sum[now]=Arr[left];
			return ; 
		}
		register int mid=(Left[now]+Right[now])>>1;
		Build(Son[now][0],left,mid);
		Build(Son[now][1],mid+1,right);
		MergeLeftRight(Data[now][0],Data[Son[now][0]][0],Data[Son[now][1]][0],Point(mid-Left[now]+1,Sum[Son[now][0]]));
		MergeLeftRight(Data[now][1],Data[Son[now][1]][1],Data[Son[now][0]][1],Point(Right[now]-mid,Sum[Son[now][1]]));
		PushUp(now);
	}
	inline Result Query(int now,int left,int right)
	{
		if(left<=Left[now]&&Right[now]<=right)
		{
			return Result(Data[now][0].MaxVal(),Data[now][1].MaxVal(),Ans[now].MaxVal(),Sum[now]+tag*(Right[now]-Left[now]+1));
		}
		register int mid=(Left[now]+Right[now])>>1;
		if(right<=mid)return Query(Son[now][0],left,right);
		else if(mid+1<=left)return Query(Son[now][1],left,right);
		else
		{
			Result tmp1=Query(Son[now][0],left,right);
			Result tmp2=Query(Son[now][1],left,right);
			return Merge(tmp1,tmp2);
		}
	}
}SegTree;
struct Operation
{
	int left,right,id;
	long long data;
	Operation(int left=0,int right=0,int id=0,long long data=0)
		:left(left),right(right),id(id),data(data){}
	inline friend bool operator<(const Operation& a,const Operation& b)
		{return a.data<b.data;} 
}Opt[600005];
int n,m,q,root;
long long ans[600005];
int main()
{
	freopen("tt.tou","r",stdin);
	freopen("tt.pot","w",stdout);
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)scanf("%lld",&Arr[i]);
	for(register int i=1;i<=m;i++)
	{
		register int opt;register long long data;scanf("%d",&opt);
		if(opt==1){scanf("%lld",&data);tag+=data;}
		else
		{
			int left,right;
			scanf("%d%d",&left,&right);
			if(left>right)std::swap(left,right);
			Opt[++q]=Operation(left,right,q,tag);
		}
	}
	std::sort(Opt+1,Opt+q+1);
	for(register int i=1;i<=n;i++)Arr[i]+=Opt[1].data;
	for(register int i=q;i>=1;i--)Opt[i].data-=Opt[1].data;
	SegTree.Build(root,1,n);
	for(register int i=1;i<=q;i++)
	{
		tag=Opt[i].data;
		ans[Opt[i].id]=SegTree.Query(root,Opt[i].left,Opt[i].right).ans;
	}
	for(register int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}