#include<bits/stdc++.h>
namespace IO
{
    template<typename T>
    inline void read(T &ans)
    {
        ans=0;
        int f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
            f=(ch=='-'?-1:f),
            ch=getchar();
        while(ch>='0'&&ch<='9')
            ans=(ans<<1)+(ans<<3)+(ch^48),
            ch=getchar();
        ans*=f;
    }
    template<typename T>
    inline void print(T x)
    {
        if(x<0)
        { x=-x; putchar('-'); }
        if(x>9) print(x/10);
        putchar(x%10^48);
    }
    template<typename T>
    inline void write(T x)
    { print(x); putchar('\n'); }
}
using namespace IO;
const int MAXN=4e5+5;
typedef long long LL;
const LL INF=1e15;
int n,m,a[MAXN];
struct Node
{
	int x; LL k;
	inline friend Node operator+(const Node &a,const Node &b)
	{ return (Node){a.x+b.x,a.k+b.k}; }
	inline void add(LL K)
	{ k+=x*K; }
};
typedef std::pair<Node,LL> PNL;
inline PNL max(Node a,Node b)
{
	if(a.x<b.x||(a.x==b.x&&a.k<b.k)) std::swap(a,b);
	if(a.k>=b.k) return std::make_pair(a,INF);
	else return std::make_pair(b,(b.k-a.k)/(a.x-b.x));
}
struct Tree
{
	LL x;
	int l,r;
	Node lmx,rmx,Tmx,sum;
	inline friend Tree operator+(const Tree &a,const Tree &b)
	{
		Tree t;
		PNL tmp;
		t.x=std::min(a.x,b.x);
		tmp=max(a.lmx,b.lmx+a.sum);
		t.lmx=tmp.first,t.x=std::min(t.x,tmp.second);
		tmp=max(b.rmx,a.rmx+b.sum);
		t.rmx=tmp.first,t.x=std::min(t.x,tmp.second);
		tmp=max(a.Tmx,b.Tmx);
		t.x=std::min(t.x,tmp.second);
		tmp=max(tmp.first,a.rmx+b.lmx);
		t.Tmx=tmp.first,t.x=std::min(t.x,tmp.second);
		t.sum=a.sum+b.sum;
		return t;
	}
};
struct KTT
{
	Tree tr[MAXN<<2];
	LL lazy[MAXN<<2];
	#define x(p) tr[p].x
	#define lmx(p) tr[p].lmx
	#define rmx(p) tr[p].rmx
	#define Tmx(p) tr[p].Tmx
	#define sum(p) tr[p].sum
	#define lzy(p) lazy[p]
	#define tr(p) tr[p]
	#define l(p) tr[p].l
	#define r(p) tr[p].r
	inline int ls(int x)
	{ return x<<1; }
	inline int rs(int x)
	{ return x<<1|1; }
	inline void pushup(int p)
	{
        int L=l(p),R=r(p);
		tr(p)=tr(ls(p))+tr(rs(p));
        l(p)=L,r(p)=R;
	}
	inline void build(int p,int l,int r)
	{
		l(p)=l,r(p)=r;
		if(l==r)
		{
			Node t={1,a[l]};
			x(p)=INF;
			lmx(p)=rmx(p)=sum(p)=Tmx(p)=t;
			return;
		}
		int mid=l+r>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		pushup(p);
	}
	inline void push(int p,LL k)
	{
		lzy(p)+=k;
		x(p)-=k;
		lmx(p).add(k);
		rmx(p).add(k);
		sum(p).add(k);
		Tmx(p).add(k);
	}
	inline void defeat(int p,LL k)
	{
		if(k>x(p))
		{
			int mid=l(p)+r(p)>>1;
			LL t=lzy(p)+k;
			lzy(p)=0;
			defeat(ls(p),k);
			defeat(rs(p),k);
			pushup(p);
		}
		else push(p,k);
	}
	inline void spread(int p)
	{
		if(lzy(p)==0) return;
		LL t=lzy(p);
		lzy(p)=0;
		push(ls(p),t);
		push(rs(p),t);
	}
	inline void modify(int p,int l,int r,LL k)
	{
		if(l<=l(p)&&r(p)<=r)
		{ defeat(p,k); return; }
		spread(p);
		int mid=l(p)+r(p)>>1;
		if(l<=mid) modify(ls(p),l,r,k);
		if(mid<r) modify(rs(p),l,r,k);
		pushup(p);
	}
	inline Tree query(int p,int l,int r)
	{
		if(l<=l(p)&&r(p)<=r) return tr(p);
		spread(p);
		int mid=l(p)+r(p)>>1;
		if(r<=mid) return query(ls(p),l,r);
		else if(mid<l) return query(rs(p),l,r);
		else return query(ls(p),l,mid)+query(rs(p),mid+1,r);
	}
}ktt;
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	ktt.build(1,1,n);
	for(int _=1,op,l,r,k;_<=m;_++)
	{
		read(op),read(l),read(r);
        if(op==1) read(k);
		if(op==1) ktt.modify(1,l,r,1LL*k);
		else write(std::max(0LL,ktt.query(1,l,r).Tmx.k));
	}
	return 0;
}

最后 4 个点我 TLE 了，能不能先帮我改成部分正确，TLE 我可以自己优化。

回复请 at 我。