P5073 一直84~92，最后一个点差60ms。

#include<bits/stdc++.h>
#define int long long
#define N 300005
#define pr pair<node,int>
#define fr first
#define sc second
#define rd read()
#define rd2 read2()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
	register int x(0),ss(1),s=gc;
	while((s<'0'||s>'9')&&s!='-')s=gc;
	if(s=='-')ss=-1,s=gc;
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=gc;
	return ss*x;
}
inline int read2()
{
	unsigned register int x(0),s=gc;
	while(s<'0'||s>'9')s=gc;
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
inline void write(int x)
{
	if(x<10){putchar(x|48);return;}
	write(x/10);
	putchar((x%10)|48);
}
const int inf=1ll<<50;
int lazy[N<<2],a[N],n,q;
int ans[N<<1];
struct qr
{
	int id,l,r,v;
	inline bool operator <(const qr &o)const{return v<o.v;}
}p[N<<1];
struct node
{
	int a,b;
	inline node operator +(const node &o)const{return {a+o.a,b+o.b};}	
};
inline pr rk(node x,node y)
{
	if(x.b==y.b)
		if(x.a<y.a)return {y,inf};
		else return {x,inf};
	if(x.b<y.b)
		if(x.a<=y.a)return {y,inf};
		else return {y,(x.b-y.b)/(y.a-x.a)};
	if(x.a>=y.a)return {x,inf};
	return {x,(y.b-x.b)/(x.a-y.a)};
}
struct seg
{
	node lmax,rmax,sum,ans;
	int fz;
	inline seg operator +(const seg &y)const
	{
		pr a=rk(lmax,sum+y.lmax),b=rk(y.rmax,rmax+y.sum),c=rk(ans,y.ans),d=rk(c.first,rmax+y.lmax);
		return {a.fr,b.fr,sum+y.sum,d.fr,min({fz,y.fz,a.sc,b.sc,c.sc,d.sc})};
	}
}tr[N<<2];
inline void pushup(int id)
{
	pr a=rk(tr[id<<1].lmax,tr[id<<1].sum+tr[id<<1|1].lmax),b=rk(tr[id<<1|1].rmax,tr[id<<1].rmax+tr[id<<1|1].sum),c=rk(tr[id<<1].ans,tr[id<<1|1].ans),d=rk(c.first,tr[id<<1].rmax+tr[id<<1|1].lmax);
	tr[id]={a.fr,b.fr,tr[id<<1].sum+tr[id<<1|1].sum,d.fr,min({tr[id<<1].fz,tr[id<<1|1].fz,a.sc,b.sc,c.sc,d.sc})};
}
inline void build(int id,int l,int r)
{
	if(l==r)
	{
		node k={1,a[l]+p[1].v};
		tr[id]={k,k,k,k,inf};
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	pushup(id);
}
inline void push(int id,int x)
{
	lazy[id]+=x,tr[id].fz-=x;
	tr[id].sum.b+=tr[id].sum.a*x;
    tr[id].ans.b+=tr[id].ans.a*x;
    tr[id].lmax.b+=tr[id].lmax.a*x;
    tr[id].rmax.b+=tr[id].rmax.a*x;
}
inline void pushdown(int id){if(lazy[id])push(id<<1,lazy[id]),push(id<<1|1,lazy[id]),lazy[id]=0;}
inline void rebuild(int id)
{
	if(tr[id].fz>=0)return;
	pushdown(id),rebuild(id<<1),rebuild(id<<1|1);
	pushup(id);
}
int x,y;
inline seg ask(int id,int l,int r)
{
	if(x<=l&&y>=r)return tr[id];
	int mid=l+r>>1;pushdown(id);
	if(x<=mid&&y>mid)return ask(id<<1,l,mid)+ask(id<<1|1,mid+1,r);
	if(x<=mid)return ask(id<<1,l,mid);
	if(y>mid)return ask(id<<1|1,mid+1,r);
}
int sum=0,ct=0;
signed main()
{
	n=rd,q=rd;cout.tie(0); 
	for(register int i(1);i<=n;++i)a[i]=rd;
	for(register int i(1);i<=q;++i)
	{
		if(rd==1)sum+=rd;
		else p[++ct]={ct,rd2,rd2,sum};
	}
	if(!ct)return 0;
	sort(p+1,p+ct+1),build(1,1,n);
	for(register int i(1);i<=ct;++i)
	{
		if(p[i].v!=p[i-1].v&&i>1)push(1,p[i].v-p[i-1].v),rebuild(1);
		x=p[i].l,y=p[i].r,ans[p[i].id]=max(0ll,ask(1,1,n).ans.b);
	}
	for(register int i(1);i<=ct;++i)write(ans[i]),putchar('\n');
	return 0;
}