RT TLE 80.

不知道是复杂度写假了还是春春常数大。

大佬帮帮qwq

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int ,int>
#define p1(x) x.first
#define p2(x) x.second
#define int long long
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct line{
    int k,b;
    inline void add(int x){
        b+=k*x;
    }
    inline int zr(){
        int t=0;
        if(k==0||(t=-b/k)<=0)return 1e18;
        return t;
    }
    friend line operator +(const line A,const line B){
        return {A.k+B.k,A.b+B.b};
    }
    friend line operator -(const line A,const line B){
        return {A.k-B.k,A.b-B.b};
    }
    
    friend int operator &(const line A,const line B){
        return (A-B).zr();
    }
};
inline line max(line A,line B){
    if(A.b==B.b){
        if(A.k>B.k)return A;
        return B;
    }
    if(A.b>B.b)return A;
    return B;
}
struct node{
    int lim;
    line s,pre,suf,mx;
    node(int x=0){
        if(x>=0){
            lim=1e18;
            s={1,x};
            pre=suf=mx={1,x};
        }
        else{
            lim=-x;
            s={1,x};
            pre=suf=mx={0,0};
        }
    }
    inline void add(int x){
        lim-=x;
        s.add(x),pre.add(x),suf.add(x),mx.add(x);
    }
    friend node operator+(const node A,const node B){
            node C;
            C.s=A.s+B.s;
            C.lim=min(A.lim,B.lim);
            line P=A.pre,Q=A.s+B.pre;
            C.pre=max(P,Q);
            C.lim=min(C.lim,P&Q);
            P=A.suf+B.s,Q=B.suf;
            C.suf=max(P,Q);
            C.lim=min(C.lim,P&Q);
            P=A.mx,Q=B.mx;
            line E=A.suf+B.pre;
            C.mx=max(E,max(P,Q));
            C.lim=min(C.lim,P&Q);
            C.lim=min(C.lim,P&E);
            C.lim=min(C.lim,E&Q);
            return C;
    }
}w[400300<<2];
int tg[400300<<2];
inline void pd(int x){
    if(tg[x]){
        tg[lc(x)]+=tg[x],tg[rc(x)]+=tg[x];
        w[lc(x)].add(tg[x]);
        w[rc(x)].add(tg[x]);
        tg[x]=0;
        
    }   
}
inline void upd(int x){
    w[x]=w[lc(x)]+w[rc(x)];
}
int a[400300];
inline void bd(int x,int l,int r){
    // cout<<l<<" "<<r<<" "<<x<<endl;
    // cout.flush();
    if(l==r){
        w[x]=node(tg[x]=a[l]);
        return ;
    }
    int mid=l+r>>1;
    bd(lc(x),l,mid);
    bd(rc(x),mid+1,r);
    upd(x);
}
inline void mod(int x,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R&&w[x].lim>k){
        tg[x]+=k;
        w[x].add(k);
        return ;
    }
    if(l==r){
        tg[x]+=k;
        w[x]=node(tg[x]);
        return ;
    }
    pd(x);
    int mid=l+r>>1;
    if(L<=mid)mod(lc(x),l,mid,L,R,k);
    if(R>mid)mod(rc(x),mid+1,r,L,R,k);
    
    upd(x);
}
inline node g(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R)return w[x];
    pd(x);
    int mid=l+r>>1;
    node P=node(0);
    if(L<=mid)P=P+g(lc(x),l,mid,L,R);
    if(R>mid)P=P+g(rc(x),mid+1,r,L,R);
    return P;
}
int n,q;
signed main(){
    // freopen("genshin.in","r",stdin);
    // freopen("genshin.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    n=rd(),q=rd();
    for(int i=1;i<=n;i++)
        a[i]=rd();
    bd(1,1,n);
    // return 0;
    while(q--){
        int op=rd();
        if(op==1){
            int l=rd(),r=rd(),x=rd();
            mod(1,1,n,l,r,x);
        }
        else{
            int l=rd(),r=rd();
            cout<<g(1,1,n,l,r).mx.b<<endl;
        }
    }
    return 0;
}