rt

调BK了

#include<bits/stdc++.h>
#define inf LONG_LONG_MAX
#define int long long
const int MAXN=4e5+5;
inline int read(){
    int x(0),f(1);
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
struct Line{
    int a,b;
    friend Line operator + (Line x,Line y){return {x.a+y.a,x.b+y.b};}    
};
int n,Q;
int a[MAXN];
std::pair <Line,int> inter(Line x,Line y){
    if(x.a<y.a||x.a==y.a&&x.b<y.b) std::swap(x,y);
    if(x.b>=y.b) return {x,inf};
    return {y,(y.b-x.b)/(x.a-y.a)};
}
struct node{
    Line l,r,sum,ans;
    int intr;
    friend node operator + (node x,node y){
        node t;
        std::pair <Line,int> tmp;
        t.intr=std::min(x.intr,y.intr);
        tmp=inter(x.l,y.l+x.sum);
        t.l=tmp.first;
        t.intr=std::min(t.intr,tmp.second);
        tmp=inter(y.r,x.r+y.sum);
        t.r=tmp.first;
        t.intr==std::min(t.intr,tmp.second);
        tmp=inter(x.ans,y.ans);
        t.intr=std::min(t.intr,tmp.second);
        tmp=inter(tmp.first,x.r+y.l);
        t.ans=tmp.first;
        t.intr=std::min(t.intr,tmp.second);
        t.sum=x.sum+y.sum;    
        return t;
    }
};
struct KTT{
    node t[MAXN<<2];
    int tag[MAXN<<2];
    inline int ls(int p){return p<<1;}
    inline int rs(int p){return p<<1|1;}
    inline void pushup(int p){t[p]=t[ls(p)]+t[rs(p)];}
    inline void addtag(int p, int x){
        tag[p]+=x,t[p].intr-=x;
        t[p].l.b+=t[p].l.a*x;
        t[p].r.b+=t[p].r.a*x;
        t[p].sum.b+=t[p].sum.a*x;
        t[p].ans.b+=t[p].ans.a*x;
    }
    inline void pushdown(int p){
        for(auto son:{ls(p),rs(p)}) addtag(son,tag[p]);
        tag[p]=0;
    }
    inline void build(int p=1,int pl=1,int pr=n){
        tag[p]=0;
        if(pl==pr){
            t[p].intr=inf;
            t[p].l=t[p].r=t[p].sum=t[p].ans={1,a[pl]};
            return;
        }
        int mid=(pl+pr)>>1;
        build(ls(p),pl,mid),build(rs(p),mid+1,pr);
        pushup(p);
    }
    inline void rebuild(int p){
        if(t[p].intr>=0) return;
        pushdown(p);
        rebuild(ls(p)),rebuild(rs(p));
        pushup(p);
    }
    inline void update(int L,int R,int x,int p=1,int pl=1,int pr=n){
        if(pl>=L&&pr<=R){
            addtag(p,x);
            rebuild(p);
            return;
        }
        pushdown(p);
        int mid=(pl+pr)>>1;
        if(L<=mid) update(L,R,x,ls(p),pl,mid);
        if(R>mid) update(L,R,x,rs(p),mid+1,pr);
        pushup(p);
    }
    inline node query(int L,int R,int p=1,int pl=1,int pr=n){
        if(pl>=L&&pr<=R) return t[p];
        pushdown(p);
        int mid=(pl+pr)>>1;
        if(R<=mid) return query(L,R,ls(p),pl,mid);
        if(L>mid) return query(L,R,rs(p),mid+1,pr);
        return query(L,R,ls(p),pl,mid)+query(L,R,rs(p),mid+1,pr);
    }
}tree;
signed main(){
    n=read(),Q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    tree.build();
    while(Q--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            int x=read();
            tree.update(l,r,x);
        }else printf("%lld\n",std::max(0ll,tree.query(l,r).ans.b));
    }
}