#include <bits/stdc++.h> using namespace std; #define int long long #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define all(a) a.begin(), a.end() #define srtvc(a) sort(all(a)) #define bcsrtvc(a) sort(all(a), greater<__typeof__(a[0])>()) #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define fr first #define sc second #define pq priority_queue #define pii pair<int, int> #define iii tuple<int, int, int> #define vc vector #define dq deque #define stk stack #define umap unordered_map #define sz(a) a.size() #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using vv = vc<vc<T>>; struct NodeA { int lv, rv, len, pref, suff, best; NodeA(): lv(0), rv(0), len(0), pref(0), suff(0), best(0) {} }; struct SegA { int n; vc<NodeA> st; vc<int> lazyAdd; vc<pair<bool, int>> lazyAssign; SegA(int _n = 0) { init(_n); } void init(int _n) { n = max(0LL, _n); if (n == 0) return; st.assign(4*n+5, NodeA()); lazyAdd.assign(4*n+5, 0); lazyAssign.assign(4*n+5, {0, 0}); } NodeA merge(const NodeA &L, const NodeA &R) { if (L.len == 0) return R; if (R.len == 0) return L; NodeA p; p.len = L.len + R.len; p.lv = L.lv; p.rv = R.rv; p.pref = L.pref; if (L.pref == L.len && L.rv == R.lv) p.pref = L.len + R.pref; p.suff = R.suff; if (R.suff == R.len && L.rv == R.lv) p.suff = R.len + L.suff; p.best = max(L.best, R.best); if (L.rv == R.lv) mxto(p.best, L.suff + R.pref); return p; } void applyAssign(int p, int l, int r, int val) { NodeA &nd = st[p]; nd.lv = nd.rv = val; nd.pref = nd.suff = nd.best = nd.len; lazyAssign[p] = {1, val}; lazyAdd[p] = 0; } void applyAdd(int p, int l, int r, int v) { NodeA &nd = st[p]; nd.lv += v; nd.rv += v; if (lazyAssign[p].fr) lazyAssign[p].sc += v; else lazyAdd[p] += v; } void build_from_array(const vc<int> &a) { if (n == 0) return; build(1, 1, n, a); } void build(int p, int l, int r, const vc<int> &a) { lazyAdd[p] = 0; lazyAssign[p] = {0, 0}; if (l == r) { NodeA &nd = st[p]; nd.len = 1; nd.lv = nd.rv = a[l]; nd.pref = nd.suff = nd.best = 1; return; } int m = (l + r)/2; build(p<<1, l, m, a); build(p<<1|1, m+1, r, a); st[p] = merge(st[p<<1], st[p<<1|1]); } void push(int p, int l, int r) { if (l == r) return; int lc = p<<1, rc = p<<1|1; if (lazyAssign[p].fr) { applyAssign(lc, l, (l+r)/2, lazyAssign[p].sc); applyAssign(rc, (l+r)/2+1, r, lazyAssign[p].sc); lazyAssign[p] = {0, 0}; } if (lazyAdd[p] != 0) { int v = lazyAdd[p]; applyAdd(lc, l, (l+r)/2, v); applyAdd(rc, (l+r)/2+1, r, v); lazyAdd[p] = 0; } } void rangeAssign(int L, int R, int val) { if (n == 0) return; rangeAssign(1, 1, n, L, R, val); } void rangeAssign(int p, int l, int r, int L, int R, int val) { if (R < l || r < L) return; if (L <= l && r <= R) { applyAssign(p, l, r, val); return; } push(p, l, r); int m = (l + r)/2; rangeAssign(p<<1, l, m, L, R, val); rangeAssign(p<<1|1, m+1, r, L, R, val); st[p] = merge(st[p<<1], st[p<<1|1]); } void rangeAdd(int L, int R, int val) { if (n == 0) return; rangeAdd(1, 1, n, L, R, val); } void rangeAdd(int p, int l, int r, int L, int R, int val) { if (R < l || r < L) return; if (L <= l && r <= R) { applyAdd(p, l, r, val); return; } push(p, l, r); int m = (l + r)/2; rangeAdd(p<<1, l, m, L, R, val); rangeAdd(p<<1|1, m+1, r, L, R, val); st[p] = merge(st[p<<1], st[p<<1|1]); } NodeA queryRange(int L, int R) { if (n == 0) return NodeA(); return queryRange(1, 1, n, L, R); } NodeA queryRange(int p, int l, int r, int L, int R) { if (R < l || r < L) return NodeA(); if (L <= l && r <= R) return st[p]; push(p, l, r); int m = (l + r)/2; NodeA a = queryRange(p<<1, l, m, L, R); NodeA b = queryRange(p<<1|1, m+1, r, L, R); return merge(a, b); } }; struct SegD { int n; struct Tag { bool hasAssign; int A, B, addA, addB; Tag(): hasAssign(0), A(0), B(0), addA(0), addB(0) {} }; vc<Tag> lazy; SegD(int _n = 0) { init(_n); } void init(int _n) { n = _n; lazy.assign(4*n+5, Tag()); } void applyAssign(int p, int a, int b) { lazy[p].hasAssign = 1; lazy[p].A = a; lazy[p].B = b; lazy[p].addA = lazy[p].addB = 0; } void applyAdd(int p, int da, int db) { if (lazy[p].hasAssign) { lazy[p].A += da; lazy[p].B += db; } else { lazy[p].addA += da; lazy[p].addB += db; } } void push(int p, int l, int r) { int m = (l + r)/2; int lc = p<<1, rc = p<<1|1; if (lazy[p].hasAssign) { int A = lazy[p].A, B = lazy[p].B; applyAssign(lc, A, B); applyAssign(rc, A, B); lazy[p].hasAssign = 0; } if (lazy[p].addA != 0 || lazy[p].addB != 0) { int addA = lazy[p].addA, addB = lazy[p].addB; applyAdd(lc, addA, addB); applyAdd(rc, addA, addB); lazy[p].addA = lazy[p].addB = 0; } } void build_from_D(const vc<int> &D) { if (n == 0) return; build(1, 1, n, D); } void build(int p, int l, int r, const vc<int> &D) { lazy[p] = Tag(); if (l == r) { applyAssign(p, D[l], 0); return; } int m = (l + r)/2; build(p<<1, l, m, D); build(p<<1|1, m+1, r, D); } void rangeAddLinear(int L, int R, int alpha, int beta) { if (L > R) return; rangeAddLinear(1, 1, n, L, R, alpha, beta); } void rangeAddLinear(int p, int l, int r, int L, int R, int alpha, int beta) { if (R < l || r < L) return; if (L <= l && r <= R) { applyAdd(p, alpha, beta); return; } push(p, l, r); int m = (l + r)/2; rangeAddLinear(p<<1, l, m, L, R, alpha, beta); rangeAddLinear(p<<1|1, m+1, r, L, R, alpha, beta); } void rangeAssignLinear(int L, int R, int alpha, int beta) { if (L > R) return; rangeAssignLinear(1, 1, n, L, R, alpha, beta); } void rangeAssignLinear(int p, int l, int r, int L, int R, int alpha, int beta) { if (R < l || r < L) return; if (L <= l && r <= R) { applyAssign(p, alpha, beta); return; } push(p, l, r); int m = (l + r)/2; rangeAssignLinear(p<<1, l, m, L, R, alpha, beta); rangeAssignLinear(p<<1|1, m+1, r, L, R, alpha, beta); } int pointQuery(int pos) { return pointQuery(1, 1, n, pos); } int pointQuery(int p, int l, int r, int pos) { if (l == r) { int res = 0; if (lazy[p].hasAssign) res = lazy[p].A + lazy[p].B * l; else res = lazy[p].addA + lazy[p].addB * l; return res; } push(p, l, r); int m = (l + r)/2; if (pos <= m) return pointQuery(p<<1, l, m, pos); else return pointQuery(p<<1|1, m+1, r, pos); } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; vc<int> D(N+1); rep(i, 1, N+1) cin >> D[i]; if (N == 1) { rep(i, 0, Q) { int t; cin >> t; if (t == 1 || t == 2) { int L, R, S, C; cin >> L >> R >> S >> C; } else { int L, R; cin >> L >> R; cout << 1 << '\n'; } } return 0; } vc<int> A(N); rep(i, 1, N) A[i] = D[i+1] - D[i]; SegA segA(N-1); segA.build_from_array(A); SegD segD(N); segD.build_from_D(D); rep(qi, 0, Q) { int type; cin >> type; if (type == 1) { int L, R, S, C; cin >> L >> R >> S >> C; int alpha = S - L*C; int beta = C; segD.rangeAddLinear(L, R, alpha, beta); if (L < R) segA.rangeAdd(L, R-1, C); if (L > 1) segA.rangeAdd(L-1, L-1, S); if (R < N) { int fR = S + (R-L)*C; segA.rangeAdd(R, R, -fR); } } else if (type == 2) { int L, R, S, C; cin >> L >> R >> S >> C; int alpha = S - L*C; int beta = C; segD.rangeAssignLinear(L, R, alpha, beta); if (L < R) segA.rangeAssign(L, R-1, C); if (L > 1) { int D_Lminus1 = segD.pointQuery(L-1); int newA = S - D_Lminus1; segA.rangeAssign(L-1, L-1, newA); } if (R < N) { int D_Rplus1 = segD.pointQuery(R+1); int DR = S + (R-L)*C; int newA = D_Rplus1 - DR; segA.rangeAssign(R, R, newA); } } else if (type == 3) { int L, R; cin >> L >> R; if (L == R) { cout << 1 << '\n'; continue; } NodeA ans = segA.queryRange(L, R-1); cout << ans.best+1 << '\n'; } } }