RT.

值域较小的巨大数据都能过的。而且不 TLE。剩下三个点就是过不了。

#include<bits/stdc++.h>
using namespace std;
#define inline __inline
constexpr int maxn=1e5+5;constexpr int maxm=1e5+5;
constexpr long long inf=1e16;
constexpr int siz=408;//有预感要大调 
//points
struct point
{
	long long x,y;
	inline point(long long xx=0,long long yy=0):x(xx),y(yy){}
	inline point operator +(point t){return point(x+t.x,y+t.y);}
	inline point operator -(point t){return point(x-t.x,y-t.y);}
};
typedef point Vector;
inline long long cross_mul(Vector x,Vector y){return x.x*y.y-x.y*y.x;}
//memory_pool
struct big_memory_pool
{
	point pool[131072];
	point* now;
	big_memory_pool(){now=pool;}
	__inline void del(point* st){now=st;}
	__inline point* get_area(int siz){static point* ans;ans=now;now+=siz;return ans;}
};
//convex_hull
struct multi_dot
{
	point* points;
	int cnt;
	int now;
	long long tag;
	multi_dot(){points=NULL,cnt=0,now=0,tag=0;}
	inline point operator [](const int &val){return points[val]+(point){0,points[val].x*tag};}
	inline void operator =(point* t){points=t;}
	inline void get_convex_hull()
	{
		if(cnt<=1)return;
		for(int i=0;i<=cnt;i++)
			if(points[i].y!=-inf)
				points[i].y+=points[i].x*tag;
		tag=0;
		int t=1;
		for(int i=2;i<=cnt;i++)
		{
			if(points[i].y==-inf)continue;
			while(t&&cross_mul(points[t]-points[t-1],points[i]-points[t-1])>=0)t--;
			points[++t]=points[i];
		}
		cnt=t;
		now=0;
	}
	inline void clear()
	{
		tag=0;
        now=0;
		points[0]={0,0};
		for(long long i=1;i<=cnt;i++)points[i]={i,-inf}; 
	}
	inline void insert(point t){points[t.x].y=max(points[t.x].y,t.y);}
	inline int size(){return cnt;}
	inline long long query(long long dx)
	{
		dx+=tag;
		while(now!=cnt&&(points[now].y+dx*points[now].x)<(points[now+1].y+dx*points[now+1].x))now++;
		return points[now].y+dx*points[now].x;
	}
	inline void pb(point t){points[++cnt]=t;}
	inline long long query_once(long long dx)
	{
		dx+=tag;
		int l=-1,r=cnt;
		while(l<r-1)
		{
			int mid=(l+r)>>1;
			if((points[mid].y+dx*points[mid].x)<(points[mid+1].y+dx*points[mid+1].x))l=mid;
			else r=mid;
		}
		return points[r].y+dx*points[r].x;
	}
};
//merge convex_hull
inline void merge(multi_dot &a,multi_dot &b,multi_dot &ans)
{
	int l=0,r=0;
	ans.insert(a[0]+b[0]);
	while(l<a.size()&&r<b.size()){ans.insert(cross_mul(a[l+1]-a[l],b[r+1]-b[r])>=0?a[l]+b[++r]:a[++l]+b[r]);}
	while(l<a.size())ans.insert(b[r]+a[++l]);
	while(r<b.size())ans.insert(a[l]+b[++r]);
}
//store ans
struct node
{
	long long ls,rs,mx,sum;
	inline node operator +(node tmp)
	{
		return (node){max(ls,sum+tmp.ls),max(tmp.rs,tmp.sum+rs),max(max(mx,tmp.mx),rs+tmp.ls),sum+tmp.sum};
	}
};
//node
struct seg_node
{
	multi_dot lft,rgt,mx;
	long long sum;
};
inline void pre_merge(multi_dot &a,multi_dot &b,multi_dot &ans,point dx)
{
	ans.cnt=-1;
	for(int i=0;i<=a.size();i++)ans.pb(a[i]);
	for(int i=1;i<=b.size();i++)ans.pb(b[i]+dx);
}
int st[maxn];
node the_ans[maxm];
struct query
{
	int l,r;
	int type;
	int dx;
}q[maxm];
struct my_vector
{
	unsigned long long a[maxm];
	int siz;
	__inline int size(){return siz;}
	__inline void push_back(unsigned long long t){a[siz++]=t;}
	__inline void clear(){siz=0;}
	__inline unsigned long long operator [](int t){return a[t];}
};
unsigned long long tmp[maxm];
unsigned int bu[1<<11];
void sort(unsigned long long *st,unsigned long long *ed,unsigned long long n,unsigned int bit)
{
	memset(bu,0,sizeof(bu));
	for(unsigned int i=0;i<n;i++)bu[(st[i]>>bit)&(0x7ff)]++;
	for(unsigned int i=1;i<(1<<11);i++)bu[i]+=bu[i-1];
	for(int i=n-1;i>=0;i--)ed[--bu[(st[i]>>bit)&0x7ff]]=st[i];
}
//sort 11 bit every time
void sort(unsigned long long *st,int n)
{
	sort(st,tmp,n,0);
	sort(tmp,st,n,11);
	sort(st,tmp,n,22);
	memcpy(tmp,st,sizeof(long long)*n);
}
//sort 33 bit.
int block_siz;
inline void sort(my_vector &qq)
{
	if(qq.siz>=1500)sort(qq.a,qq.siz);
	else sort(qq.a,qq.a+qq.siz,[](unsigned long long a,unsigned long long b){return (a&0x1ffffffff)<(b&0x1ffffffff);});//lambda!
}
int n,m;
struct seg
{
	big_memory_pool pool;
	seg_node nodes[maxn<<2];
	my_vector now_q;
	long long lazy[maxn<<2];
	__inline int ls(int x){return x<<1;}__inline int rs(int x){return (x<<1)|1;}
	inline void push_up(int now,int l,int r)
	{
		seg_node& lt=nodes[ls(now)],&rt=nodes[rs(now)];
		seg_node& ans=nodes[now];
        ans.lft.cnt=ans.rgt.cnt=ans.mx.cnt=r-l+1;
        ans.lft.clear(),ans.rgt.clear(),ans.mx.clear();
		int mid=(l+r)>>1;
		pre_merge(lt.lft,rt.lft,ans.lft,(point){mid-l+1,lt.sum});
		pre_merge(rt.rgt,lt.rgt,ans.rgt,(point){r-mid,rt.sum});
		for(int i=0;i<=lt.mx.size();i++)ans.mx.insert(lt.mx[i]);
		for(int i=0;i<=rt.mx.size();i++)ans.mx.insert(rt.mx[i]);
		merge(lt.rgt,rt.lft,ans.mx);
		ans.sum=lt.sum+rt.sum;
		ans.mx.get_convex_hull();ans.lft.get_convex_hull();ans.rgt.get_convex_hull();
	}
	inline void init(int now,int l,int r)
	{
		seg_node &ans=nodes[now];
		ans.lft=pool.get_area(r-l+2);ans.rgt=pool.get_area(r-l+2);ans.mx=pool.get_area(r-l+2);
		if(l==r)return;
		int mid=(l+r)>>1;
		init(ls(now),l,mid);
		init(rs(now),mid+1,r);
	}
	inline void build(int now,int l,int r,int *st)
	{
        lazy[now]=0;
		if(l==r)
		{
			seg_node &ans=nodes[now];
			ans.lft.cnt=1;ans.rgt.cnt=1;ans.mx.cnt=1;
			ans.lft.clear();ans.rgt.clear();ans.mx.clear();
			ans.lft.insert({0,0});ans.lft.insert({1,st[l]});
			ans.rgt.insert({0,0});ans.rgt.insert({1,st[l]});
			ans.mx.insert({0,0});ans.mx.insert({1,st[l]});
			ans.sum=st[l];
			return;
		}
		int mid=(l+r)>>1;
		build(ls(now),l,mid,st);
		build(rs(now),mid+1,r,st);
		push_up(now,l,r);
	}
	__inline void all_query(int t)
	{
		now_q.push_back((t*1ull<<33)+0x100000000ull+lazy[1]);//big enough
	}
	__inline void add_tag(int now,int l,int r,long long tag)
	{
		lazy[now]+=tag;
		nodes[now].lft.tag+=tag;nodes[now].rgt.tag+=tag;nodes[now].mx.tag+=tag;
		nodes[now].sum+=(r-l+1)*tag;
	}
	__inline void all_change(int ddx)
	{
		add_tag(1,1,block_siz,ddx);
	}
	__inline void push_down(int now,int l,int r)
	{
		if(!lazy[now])return;
		int mid=(l+r)>>1;
		add_tag(ls(now),l,mid,lazy[now]);
		add_tag(rs(now),mid+1,r,lazy[now]);
		lazy[now]=0;
	}
	__inline void query(int now,int l,int r,int ql,int qr,int id,long long now_dx)
	{
		if(ql<=l&&r<=qr)
		{
			node tmp=
				{nodes[now].lft.query_once(now_dx),nodes[now].rgt.query_once(now_dx),nodes[now].mx.query_once(now_dx),nodes[now].sum+now_dx*(r-l+1)};
			the_ans[id]=the_ans[id]+tmp;
//			cout<<now<<' '<<l<<' '<<r<<' '<<tmp.ls<<' '<<tmp.rs<<' '<<tmp.mx<<' '<<now_dx<<" "<<nodes[now].lft.tag<<'\n';
			return;
		}//push_down(now,l,r);
		int mid=(l+r)>>1;
		if(ql<=mid)query(ls(now),l,mid,ql,qr,id,now_dx+lazy[now]);
		if(mid<qr)query(rs(now),mid+1,r,ql,qr,id,now_dx+lazy[now]);
	}
	inline void change(int now,int l,int r,int ql,int qr,long long dx)
	{
		if(ql<=l&&r<=qr)
		{
			add_tag(now,l,r,dx);
			return;
		}
		push_down(now,l,r);
		int mid=(l+r)>>1;
		if(ql<=mid)change(ls(now),l,mid,ql,qr,dx);
		if(mid<qr)change(rs(now),mid+1,r,ql,qr,dx);
		push_up(now,l,r);
	}
	__inline void change(int ql,int qr,long long dx)
	{
		sort(now_q);
		seg_node res=nodes[1];res.sum-=res.lft.tag*block_siz,res.lft.tag=res.rgt.tag=res.mx.tag=0;
		for(int i=0;i<now_q.size();i++)
		{
			long long tmp=now_q[i]&0x1ffffffffull;
			tmp-=0x100000000ull;
			the_ans[now_q[i]>>33]=
				the_ans[now_q[i]>>33]+(node){res.lft.query(tmp),res.rgt.query(tmp),res.mx.query(tmp),res.sum+tmp*block_siz};
		}
		now_q.clear();
		change(1,1,block_siz,ql,qr,dx);
	}
}tree;
signed main()
{
	freopen("data.txt","r",stdin);freopen("data.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>st[i];
	for(int i=1;i<=m;i++)
		(cin>>q[i].type>>q[i].l>>q[i].r),q[i].type==1?(cin>>q[i].dx),0:0;
	for(int l=1;l<=n;l+=siz)
	{
		int r=min(l+siz-1,n);
		block_siz=r-l+1;
		if(block_siz!=siz||l==1)
			tree.pool.del(tree.pool.pool),tree.init(1,1,block_siz);
		tree.build(1,1,block_siz,st+l-1);
		for(int x=1;x<=m;x++)
		{
			if(q[x].r<l||r<q[x].l)continue;
			else if(q[x].type==1)
				if(q[x].l<=l&&r<=q[x].r)
					tree.all_change(q[x].dx);
				else
					tree.change(max(q[x].l-l+1,1),min(q[x].r-l+1,block_siz),q[x].dx);
			else
				if(q[x].l<=l&&r<=q[x].r)
					tree.all_query(x);
				else
					tree.query(1,1,block_siz,max(q[x].l-l+1,1),min(q[x].r-l+1,block_siz),x,0);
		}
        tree.change(1,block_siz,0);
	}
	for(int i=1;i<=m;i++)
		if(q[i].type==2)cout<<the_ans[i].mx<<'\n';
	return 0;
}