代码稍微有亿点点长……

#include <iostream>
#include <cstdlib> 
#include <set>
using namespace std;
const int Q = 2e5 + 5;
const int N = 1e5 + 5;
typedef long long ll;
int op[Q] , ql[Q] , qr[Q] , qx[Q] , c[N];
int n , q;
void write(ll x){
    if (x < 0){
        putchar('-');
        write(-x);
    }
    else if (x < 10) putchar(x ^ 48);
    else{
        write(x / 10);
        putchar(x % 10 ^ 48);
    }
}
int read(){
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') f = 1;
        ch = getchar();
    }
    int ret = 0;
    while (ch >= '0' && ch <= '9'){
        ret = (ret << 3) + (ret << 1) + (ch ^ 48);
        ch = getchar();
    }
    if (f) ret = -ret;
    return ret;
}
namespace one{
    struct node{
        int l , r;
        mutable ll v;
        node(int L , int R = -1 , ll V = -1){
            l = L , r = R , v = V;
        }
    };
    bool operator < (const node &x , const node &y){
        return x.l < y.l;
    }
    typedef set <node> :: iterator IT;

    set <node> s , t;
    ll dp[N];

    IT split(int pos){
        IT it = s.lower_bound(pos);
        if (it != s.cend() && it -> l == pos) return it;
        --it;
        int l = it -> l , r = it -> r;
        ll v = it -> v;
        s.erase(it);
        s.insert(node(l , pos - 1 , v));
        return s.insert(node(pos , r , v)).first;
    }
    void assign(int a , int b , ll d){
        IT itr = split(b + 1);
        IT itl = split(a);
        for (IT it = itl;it != itr;++it){
            it -> v = max(it -> v , d);
        }
    }
    ll query(int a , int b){
        IT itr = split(b + 1);
        IT itl = split(a);
        int cnt = 0;
        ll ans = 0;
        for (IT it = itl;it != itr;++it){
            ++cnt;
            dp[cnt] = max(dp[cnt - 1] , 0ll) + (it -> r - it -> l + 1) * (it -> v);
            ans = max(ans , it -> v);
            ans = max(ans , dp[cnt]);
        }
        return ans;
    }
    void rebuild(){
        int x;
        ll y;
        IT it = s.begin();
        x = it -> l;
        y = it -> v;
        ++it;
        for (;it != s.cend();++it){
            if (y != (it -> v)){
                t.insert(node(x , (it -> l) - 1 , y));
                x = it -> l;
                y = it -> v;
            }
        }
        t.insert(node(x , n , y));
        s.clear();
        for (IT i = t.begin();i != t.cend();++i){
            s.insert(node(i -> l , i -> r , i -> v));
        }
        t.clear();
    }
    void solve(){
        for (int i = 1;i <= n;i++){
            s.insert(node(i , i , c[i]));
        }
        rebuild();
        srand(time(NULL));
        for (int i = 1;i <= q;i++){
            if (!(rand() & 63)) rebuild();
            if (op[i] == 0){
                assign(ql[i] , qr[i] , qx[i]);
            }
            else{
                write(query(ql[i] , qr[i]));
                putchar('\n');
            }

        }
    }
}
namespace two{
    struct node{
        int l , r;
        ll val0 , val1 , val2 , val3;
    }t[N << 2];
    //val0：ans,val1：左起ans,val2：右起ans,val3：sum
    void pushup(int x){
        t[x].val0 = max(max(t[x << 1].val0 , t[x << 1 | 1].val0) , t[x << 1].val2 + t[x << 1 | 1].val1);
        t[x].val1 = max(t[x << 1].val1 , t[x << 1].val3 + t[x << 1 | 1].val1);
        t[x].val2 = max(t[x << 1 | 1].val2 , t[x << 1 | 1].val3 + t[x << 1].val2);
        t[x].val3 = t[x << 1].val3 + t[x << 1 | 1].val3;
    }
    void build(int x , int l , int r){
        t[x].l = l , t[x].r = r;
        if (l == r){
            t[x].val0 = t[x].val1 = t[x].val2 = t[x].val3 = c[l];
            return;
        }
        int m = l + r >> 1;
        build(x << 1 , l , m);
        build(x << 1 | 1 , m + 1 , r);
        pushup(x);
    }
    node query(int x , int a , int b){
        int l = t[x].l , r = t[x].r;
        if (a <= l && r <= b) return t[x];
        int m = l + r >> 1;
        if (b <= m) return query(x << 1 , a , b);
        if (m < a) return query(x << 1 | 1 , a , b);
        node ls = query(x << 1 , a , b),rs = query(x << 1 | 1 , a , b) , ans;
        ans.val0 = max(max(ls.val0 , rs.val0) , ls.val2 + rs.val1);
        ans.val1 = max(ls.val1 , ls.val3 + rs.val1);
        ans.val2 = max(rs.val2 , rs.val3 + ls.val2);
        ans.val3 = ls.val3 + rs.val3;
        return ans;
    }
    void update(int x , int y , ll d){
        int l = t[x].l , r = t[x].r;
        if (l == r){
            t[x].val0 = t[x].val1 = t[x].val2 = t[x].val3 = max(t[x].val3 , d);
            return;
        }
        int m = l + r >> 1;
        if (y <= m) update(x << 1 , y , d);
        else update(x << 1 | 1 , y , d);
        pushup(x);
    }
    void solve(){
        build(1 , 1 , n);
        for (int i = 1;i <= q;i++){
            if (op[i] == 1){
                write(max(0ll , query(1 , ql[i] , qr[i]).val0));
                putchar('\n');
        	}
            else{
                for (int j = ql[i];j <= qr[i];++j)update(1 , j , qx[i]);
            }
        }
    }
}
int main(){
    n = read();
    q = read();
    for (int i = 1;i <= n;i++) c[i] = read();
    ll f = 0;
    for (int i = 1;i <= q;i++){
    	op[i] = read();
    	ql[i] = read();
    	qr[i] = read();
        if (!op[i]){
            qx[i] = read();
            f += qr[i] - ql[i] + 1;
    	}
	}
    if (f <= 15e5) two::solve();
    else one::solve();
    return 0;
}