100分，hack数据T了

Code

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define inf LONG_LONG_MAX
#define rd read() 
ll lazy[N<<2],l,r,v,n,m,a[N],op;
using namespace std;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct line{//ax+b
	ll a,b;
	line operator + (const line &x) const{
		return {a+x.a,b+x.b};
	}
	inline void add(ll v){
		b+=v*a;
	}
	inline void clear(){
		a=0;
	}
};
pair<line,ll> chenk(line x,line y){
	if(x.a<y.a||(x.a==y.a&&x.b<y.b)) swap(x,y);
	if(x.b>=y.b) return make_pair(x,inf);
	return make_pair(y,(y.b-x.b)/(x.a-y.a));
}
struct node{
	line lmx,rmx,sum,mx;
	ll t,mn,semn;	
	inline node clear(){
		node a=*this;
		a.lmx.clear(),a.rmx.clear(),a.mx.clear(),a.sum.clear();
		return a;
	}
	node operator + (const node &x) const{
		node res;
		pair<line,ll> tmp;
		res.t=min(t,x.t);		
		res.sum=sum+x.sum;		
		tmp=chenk(lmx,x.lmx+sum);		
		res.lmx=tmp.first,res.t=min(res.t,tmp.second);	
		tmp=chenk(x.rmx,rmx+x.sum);		
		res.rmx=tmp.first,res.t=min(res.t,tmp.second);		
		tmp=chenk(mx,x.mx);		
		res.t=min(res.t,tmp.second);		
		tmp=chenk(tmp.first,rmx+x.lmx);		
		res.mx=tmp.first,res.t=min(res.t,tmp.second);
		return res;
	}

}tr[N<<2];
inline void pushup(ll k){	
	node y=tr[k<<1],x=tr[k<<1|1],res;
	if(y.mn==x.mn){
		res=tr[k<<1]+tr[k<<1|1];
		res.mn=y.mn;
		res.semn=min(y.semn,x.semn);	
	}
	else if(y.mn<x.mn){	
		res=tr[k<<1]+tr[k<<1|1].clear();
		res.mn=y.mn;
		res.semn=min(x.mn,y.semn);	
	}
	else{
		res=tr[k<<1].clear()+tr[k<<1|1];		
		res.mn=x.mn;
		res.semn=min(x.mn,x.semn);
	}
	tr[k]=res;
}
inline void add(ll k,ll w){
	if(w<=tr[k].mn) return;
	lazy[k]=max(lazy[k],w);
	ll v=w-tr[k].mn;
	tr[k].mn=w;
	tr[k].t-=v;
	tr[k].lmx.add(v);
	tr[k].rmx.add(v);
	tr[k].sum.add(v);
	tr[k].mx.add(v);
}
inline void upd(ll k,ll v){
	lazy[k]=max(lazy[k],v); 
	if(v-tr[k].mn>tr[k].t){
		upd(k<<1,v);
		upd(k<<1|1,v);
		pushup(k);
	}
	else{
		add(k,v);
	}
}
inline void pushdown(ll k){
	if(lazy[k]!=inf){
		add(k<<1,lazy[k]);
		add(k<<1|1,lazy[k]);
		lazy[k]=-inf;
	}
}
inline void build(ll k,ll l,ll r){
	lazy[k]=-inf;
	if(l==r){
		tr[k].lmx=tr[k].rmx=tr[k].mx=tr[k].sum={1,a[l]};
		tr[k].mn=a[l];
		tr[k].semn=inf;
		tr[k].t=inf;
		return;
	}
	ll mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
inline void update(ll k,ll l,ll r,ll x,ll y,ll v){
	if(tr[k].mn>=v) return;
	if(x<=l&&r<=y&&v<tr[k].semn){
		upd(k,v); 
		return;
	}
	pushdown(k);
	ll mid=l+r>>1;
	if(x<=mid) update(k<<1,l,mid,x,y,v);
	if(mid<y) update(k<<1|1,mid+1,r,x,y,v);
	pushup(k);
}
inline node query(ll k,ll l,ll r,ll x,ll y){
	if(x<=l&&r<=y){
		return tr[k];
	}
	pushdown(k);
	ll mid=l+r>>1;
	if(!(x<=mid)) return query(k<<1|1,mid+1,r,x,y);
	if(!(mid<y)) return query(k<<1,l,mid,x,y);
	return query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y);
}
int main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	n=rd,m=rd;
	for(ll i=1;i<=n;++i){
		a[i]=rd;
	} 
	build(1,1,n);
	for(ll i=1;i<=m;++i){
		op=rd,l=rd,r=rd;
		if(op==0){
			v=rd;
			update(1,1,n,l,r,v);
		}
		else{
			cout<<(max(0ll,query(1,1,n,l,r).mx.b));
		}
	}
	return 0;	
}