#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() struct DSegTree{ struct Node{ int pval, sval, pf, sf, sub, lazyadd = 0, len, sum; bool set0 = false; Node(int pv, int sv, int pf, int sf, int sub, int lza, int len, int sum, bool set0) : pval(pv), sval(sv), pf(pf), sf(sf), sub(sub), lazyadd(lza), len(len), sum(sum), set0(set0) {} Node() : Node(0, 0, 0, 0, 0, 0, 0, 0, false) {} }; int n; vector<Node> st; DSegTree(int n) : n(n), st(4 * n) {} inline Node combine(const Node &a, const Node &b){ Node c; c.sum = a.sum + b.sum; c.len = a.len + b.len; c.pval = a.pval, c.sval = b.sval; c.pf = a.pf; if(a.len == a.pf && a.sval == b.pval){ c.pf = a.len + b.pf; } c.sf = b.sf; if(b.len == b.sf && a.sval == b.pval){ c.sf = b.len + a.sf; } c.sub = max({c.sf, c.pf, a.sub, b.sub}); if(a.sval == b.pval){ c.sub = max(c.sub, a.sf + b.pf); } return c; } inline void apply(int v, int addval, bool set0){ if(set0){ st[v].pval = st[v].sval = st[v].lazyadd = st[v].sum = 0; st[v].pf = st[v].sf = st[v].sub = st[v].len; st[v].set0 = true; return; } st[v].pval += addval, st[v].sval += addval, st[v].lazyadd += addval, st[v].sum += st[v].len * addval; return; } inline void propagate(int v){ if(st[v].set0){ apply(2 * v, 0, true); apply(2 * v + 1, 0, true); } apply(2 * v, st[v].lazyadd, false); apply(2 * v + 1, st[v].lazyadd, false); st[v].lazyadd = 0; st[v].set0 = false; return; } inline void build(int v, int tl, int tr, const vi &a){ if(tl == tr){ st[v] = {a[tl - 1], a[tl - 1], 1, 1, 1, 0, 1, a[tl - 1], false}; return; } int mid = (tl + tr) / 2; build(2 * v, tl, mid, a); build(2 * v + 1, mid + 1, tr, a); st[v] = combine(st[2 * v], st[2 * v + 1]); return; } inline void build(const vi &a){ build(1, 1, n, a); } inline void update(int ul, int ur, int add, bool set0, int v, int tl, int tr){ if(ul > tr || tl > ur) return; if(ul <= tl && tr <= ur){ apply(v, add, set0); return; } int mid = (tl + tr) / 2; propagate(v); if(ur <= mid){ update(ul, ur, add, set0, 2 * v, tl, mid); } else if(mid + 1 <= ul){ update(ul, ur, add, set0, 2 * v + 1, mid + 1, tr); } else{ update(ul, ur, add, set0, 2 * v, tl, mid); update(ul, ur, add, set0, 2 * v + 1, mid + 1, tr); } st[v] = combine(st[2 * v], st[2 * v + 1]); return; } inline void update(int ul, int ur, int add, bool set0){ update(ul + 1, ur + 1, add, set0, 1, 1, n); } inline Node query(int ql, int qr, int v, int tl, int tr){ if(ql > tr || tl > qr) return Node(); if(ql <= tl && tr <= qr) return st[v]; int mid = (tl + tr) / 2; propagate(v); if(qr <= mid){ return query(ql, qr, 2 * v, tl, mid); } else if(mid + 1 <= ql){ return query(ql, qr, 2 * v + 1, mid + 1, tr); } else{ return combine(query(ql, qr, 2 * v, tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr)); } } inline int query(int ql, int qr){ return query(ql + 1, qr + 1, 1, 1, n).sub; } inline int querysum(int ql, int qr){ return query(ql + 1, qr + 1, 1, 1, n).sum; } inline int query(int pos){ return query(1, pos + 1, 1, 1, n).sum; } }; inline void solve(){ int n, q; cin >> n >> q; vi a(n), d(n - 1); for(int i = 0; i < n; i++){ cin >> a[i]; if(i){ d[i - 1] = a[i] - a[i - 1]; } } if (n == 1) { while (q--) { int type; cin >> type; if (type == 3) { int l, r; cin >> l >> r; cout << 1 << "\n"; } else { int L, R, S, C; cin >> L >> R >> S >> C; } } return; } DSegTree dseg(n - 1); dseg.build(d); auto patch = [&](int l, int r, int s, int c) -> void { if(l){ dseg.update(l - 1, l - 1, s, false); } if(l < r){ dseg.update(l, r - 1, c, false); } if(r + 1 < n){ dseg.update(r, r, -s - (r - l) * c, false); } if(!l){ a[0] += s; } return; }; auto rewrite = [&](int l, int r, int s, int c) -> void { if(r + 1 < n){ int afa = a[0] + dseg.query(r); //cout << "afa: " << afa << "\n"; dseg.update(r, r, 0, true); dseg.update(r, r, afa - s + (r - l) * c, false); } if(l){ int befa = a[0] + (l >= 2 ? dseg.query(l - 2) : 0); //cout << "a: " << a[0] << " diffs: " << dseg.query(l - 1) << " befa: " << befa << "\n"; dseg.update(l - 1, l - 1, 0, true); dseg.update(l - 1, l - 1, s - befa, false); } if(l < r){ dseg.update(l, r - 1, 0, true); dseg.update(l, r - 1, c, false); } if(!l){ a[0] = s; } return; }; auto evaluate = [&](int l, int r) -> int { int ans = 0; if(l < r){ ans = max(ans, dseg.query(l, r - 1)); //cout << "l: " << l << " r: " << r << " dseg: " << dseg.query(l, r - 1) << "\n"; } return ans + 1; }; auto coutd = [&]() -> void { for(int i = 0; i < n - 1; i++){ cout << dseg.querysum(i, i) << " "; } cout << "\n"; return; }; while(q--){ int type, l, r; cin >> type >> l >> r; l--, r--; if(type == 1){ int s, c; cin >> s >> c; patch(l, r, s, c); } else if(type == 2){ int s, c; cin >> s >> c; //coutd(); rewrite(l, r, s, c); //coutd(); } else{ cout << evaluate(l, r) << "\n"; } } return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }