90分，真调不动了。。。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10, M = 1e5 + 10;
int n, x, y, k, m, a[N], op;
struct node {
    int l, r, maxx, lz1, lz2;
    //lz1修改
    //lz2加法
}t[N << 2];
void up(int x) {
    t[x].maxx = max(t[x << 1].maxx, t[x << 1 | 1].maxx);
}
void build(int x, int l, int r) {
    t[x] = { l,r,LLONG_MIN,0,0 };
    if (l == r) {
        t[x].maxx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    up(x);
}
void pushdown(int x) {
    int l = x << 1, r = x << 1 | 1;
    if (t[x].lz1) {//修改
        t[l].maxx = t[x].lz1;
        t[l].lz1 = t[x].lz1;
        t[l].lz2 = 0;
        t[r].maxx = t[x].lz1;
        t[r].lz1 = t[x].lz1;
        t[r].lz2 = 0;
        t[x].lz1 = 0;
    }
    if (t[x].lz2) {//加法
        t[l].maxx += t[x].lz2;
        if(t[l].lz1)t[l].lz1 += t[x].lz2;
        else t[l].lz2 += t[x].lz2;
        t[r].maxx += t[x].lz2;
        if (t[r].lz1)t[r].lz1 += t[x].lz2;
        else t[r].lz2 += t[x].lz2;

        t[x].lz2 = 0;
    }
}

void update(int x, int ul, int ur, int k) {
    int l = t[x].l, r = t[x].r;
    int mid = (l + r) >> 1;
    if (ul <= l && ur >= r) {
        t[x].maxx = k;
        t[x].lz1 = k;
        t[x].lz2 = 0;
        return;
    }
    pushdown(x);
    if (mid >= ul)update(x << 1, ul, ur, k);
    if (mid < ur)update(x << 1 | 1, ul, ur, k);
    up(x);
}
void add(int x, int al, int ar, int k) {
    int l = t[x].l, r = t[x].r;
    int mid = (l + r) >> 1;
    if (al <= l && ar >= r) {
        t[x].maxx += k;
        if (t[x].lz1)t[x].lz1 += k;
        else t[x].lz2 += k;
        return;
    }
    pushdown(x);
    if (mid >= al)add(x << 1, al, ar, k);
    if (mid < ar)add(x << 1 | 1, al, ar, k);
    up(x);
}
int query_max(int x, int ql, int qr) {
    int l = t[x].l, r = t[x].r;
    if (ql > r || qr < l)return LLONG_MIN;
    if (ql <= l && qr >= r)return t[x].maxx;
    pushdown(x);
    return max(query_max(x << 1, ql, qr), query_max(x << 1 | 1, ql, qr));
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    build(1, 1, n);
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            update(1, x, y, k);
        }
        else if (op == 2) {
            cin >> x >> y >> k;
            add(1, x, y, k);
        } 
        else if (op == 3) {
            cin >> x >> y;
            cout << query_max(1, x, y) << endl;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //int T;cin>>T;
    int T = 1;
    while (T--) solve();
    return 0;
}