卡了好久常了

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0,f = 1;
	while(c < '0' || c > '9'){
		if (c == '-')
			f = -1;
		c = gc();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x * f;
}
int read2(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
typedef long long ll;
const int N = 4e5 + 9;
const ll INF = 1e15;
int n,m;
int a[N];
struct linear_func{
	int k;
	ll b;
	inline void add(ll v){
		b += k * v;
	}
};
inline linear_func operator+(linear_func f1,linear_func f2){//两个一次函数相加
	return (linear_func){f1.k + f2.k,f1.b + f2.b};
}
inline linear_func Max(linear_func f1,linear_func f2){//返回两个一次函数在 x = 0 处取值更优者及两函数交点坐标
	return (f1.b >= f2.b) ? f1 : f2;
}
inline ll intersection(linear_func f1,linear_func f2){
	if(f1.k == f2.k && f1.b != f2.b)
		return INF;
	if(f1.k < f2.k)//保证f1.k > f2.k
		swap(f1,f2);
	if(f1.b >= f2.b)
		return INF;
	return (f2.b - f1.b) / (f2.k - f1.k);
}
struct node{
	linear_func sum,val;//区间和、区间最大子段和 
	linear_func lsum,rsum;//前缀最大和、后缀最大和 
	ll x;
};
inline node operator+(node lc,node rc){
	node ret;
	ret.x = min(lc.x,rc.x);
	ret.x = min(ret.x,intersection(lc.val,rc.val));
	ret.x = min(ret.x,intersection(Max(lc.val,rc.val),lc.rsum + rc.lsum));
	ret.x = min(ret.x,intersection(lc.lsum,lc.sum + rc.lsum));
	ret.x = min(ret.x,intersection(rc.rsum,rc.sum + lc.rsum));
	ret.sum = lc.sum + rc.sum; 
	ret.val = Max(Max(lc.val,rc.val),lc.rsum + rc.lsum);
	ret.lsum = Max(lc.lsum,lc.sum + rc.lsum);
	ret.rsum = Max(rc.rsum,rc.sum + lc.rsum);
	return ret;
}
struct KTT{
	struct ktt_node{
		node u;
		ll tag;
	} t[N << 2];
	inline bool in_range(int l,int r,int L,int R){
		return L <= l && r <= R;
	}
	inline bool out_range(int l,int r,int L,int R){
		return r < L || l > R;
	}
	inline void push_up(int root){
		t[root].u = t[lchild].u + t[rchild].u;
	}
	inline void make_tag(int root,ll v){
		t[root].tag += v;
		t[root].u.x -= v;
		t[root].u.sum.add(v);
		t[root].u.val.add(v);
		t[root].u.lsum.add(v);
		t[root].u.rsum.add(v);
	}
	inline void push_down(int root){
		if(t[root].tag){
			make_tag(lchild,t[root].tag);
			make_tag(rchild,t[root].tag);
			t[root].tag = 0;
		}
	}
	inline void defeat(int root,int l,int r,ll v){
		if(v > t[root].u.x){
			t[root].tag = 0;
			defeat(lchild,l,mid,t[root].tag + v);
			defeat(rchild,mid + 1,r,t[root].tag + v);
			push_up(root);
		}
		else
			make_tag(root,v);
	}
	inline void build(int root,int l,int r){
		if(l == r){
			linear_func tmp = (linear_func){1,a[l]};
			t[root].u = (node){tmp,tmp,tmp,tmp,INF};//该题的最大子段和不能不选，所以单位长度的区间最大子段和为该位置上的值 
			return;
		}
		build(lchild,l,mid);
		build(rchild,mid + 1,r);
		push_up(root);
	}
	inline void update(int root,int l,int r,int L,int R,int v){
		if(out_range(l,r,L,R))
			return;
		if(in_range(l,r,L,R)){
			defeat(root,l,r,v);
			return;
		}
		push_down(root);
		update(lchild,l,mid,L,R,v);
		update(rchild,mid + 1,r,L,R,v);
		push_up(root);
	}
	inline node query(int root,int l,int r,int L,int R){
		if(in_range(l,r,L,R))
			return t[root].u;
		push_down(root);
		if(R <= mid)
			return query(lchild,l,mid,L,R);
		if(L > mid)
			return query(rchild,mid + 1,r,L,R);
		return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
	}
} ktt;
signed main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read2();m = read2();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	ktt.build(1,1,n);
	while(m--){
		int op = read2();
		if(op == 1){
			int l = read2(),r = read2(),v = read2();
			ktt.update(1,1,n,l,r,v);
		}
		else if(op == 2){
			int l = read2(),r = read2();
			cout << max(ktt.query(1,1,n,l,r).val.b,0ll) << '\n';
		}
	}
	return 0;
}