#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int, int> #define bend(v) v.begin(),v.end() #define vect vector #define prq priority_queue #define umap unordered_map #define eb emplace_back #define pb push_back #define pob pop_back #define ef emplace_front #define pf push_front #define pof pop_front #define el "\n" #define deb cout<<"\nok\n";return #define nextl cout<<"\n" #define lwb lower_bound #define upb upper_bound #define rs resize #define popcnt __builtin_popcount #define clz __builtin_clz #define ctz __builtin_ctz #define ll long long #define dbl long double #define int long long #define FILE "ijustwannabepartofyourskibidi" void IO(){ if(fopen(FILE".in", "r")){ freopen(FILE".in", "r", stdin); freopen(FILE".out", "w", stdout); } else if(fopen(FILE".inp", "r")){ freopen(FILE".inp", "r", stdin); freopen(FILE".out", "w", stdout); } } const ll N = 3e5 + 69, MOD = 1e9+7, INF = 1000000000000000069; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rand(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } ll pm(ll a,const ll b=MOD){return ((a%b)+b)%b;} ll sq(ll x){return x*x;} ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){ if(a == -1 || b == -1)return -1; ll g = __gcd(a,b); if(b/g > lim/a)return -1; return (a/g)*b; } int n, a[N], d[N], q; struct node{ int preval, sufval, prelen, suflen, len, mx, sum; void init(int pv, int sv, int pl, int sl, int l, int m, int s){ preval = pv ; sufval = sv ; prelen = pl ; suflen = sl ; len = l ; mx = m ; sum = s; } node operator + (const node& o) const{ node res;res.mx = max(mx, o.mx); if(sufval == o.preval) res.mx = max(res.mx, suflen + o.prelen); res.prelen = prelen; res.suflen = o.suflen; if(prelen == len && preval == o.preval){ res.mx = max(res.mx, prelen + o.prelen); res.prelen += o.prelen; } if(o.suflen == o.len && o.sufval == sufval){ res.mx = max(res.mx, o.prelen + suflen); res.suflen += suflen; } res.len = len + o.len; res.preval = preval; res.sufval = o.sufval; res.sum = sum + o.sum; return res; } }; struct Seggs{ vect<int> lz1, lz2; vect<node> t; Seggs(){ t.rs(4*N); lz1.rs(4*N, 0); lz2.rs(4*N, INF); build(); } void build(int l=1, int r=n-1, int id=1){ if(l == r){ // cout << d[l] << ' '; t[id].init(d[l], d[l], 1, 1, 1, 1, d[l]); return; } int mid = (l+r)/2; build(l, mid, id*2); build(mid+1, r, id*2+1); t[id] = t[id*2] + t[id*2+1]; // cout << l << ' ' << r << ' ' << t[id].mx << ' ' << t[id].prelen << el; } void push(int l, int r, int id){ if(lz2[id] != INF){ t[id].preval = lz2[id]; t[id].sufval = lz2[id]; t[id].sum = lz2[id] * t[id].len; t[id].mx = t[id].prelen = t[id].suflen = t[id].len; if(l < r){ lz2[id*2] = lz2[id]; lz2[id*2+1] = lz2[id]; lz1[id*2] = 0; lz1[id*2+1] = 0; } lz2[id] = INF; } t[id].preval += lz1[id]; t[id].sufval += lz1[id]; t[id].sum += lz1[id] * t[id].len; if(l < r){ lz1[id*2] += lz1[id]; lz1[id*2+1] += lz1[id]; } lz1[id] = 0; } void add(int i, int j, int x, int l=1, int r=n-1, int id=1){ push(l, r, id); if(l > j || r < i) return; if(i <= l && r <= j){ lz1[id] += x; push(l, r, id); return; } int mid = (l+r)/2; add(i, j, x, l, mid, id*2); add(i, j, x, mid+1, r, id*2+1); t[id] = t[id*2] + t[id*2+1]; } void assign(int i, int j, int x, int l=1, int r=n-1, int id=1){ push(l, r, id); if(l > j || r < i) return; if(i <= l && r <= j){ lz2[id] = x; push(l, r, id); // cout << "hm " << l << ' ' << r << ' ' << t[id].mx << ' ' << t[id].preval << ' ' << t[id].sufval << el; return; } int mid = (l+r)/2; assign(i, j, x, l, mid, id*2); assign(i, j, x, mid+1, r, id*2+1); t[id] = t[id*2] + t[id*2+1]; // cout << "hm " << l << ' ' << r << " pre: " << t[id].preval << ' ' << t[id].prelen << " suf: " << t[id].sufval << ' ' << t[id].suflen << el; } int get_sum(int i, int j, int l=1, int r=n-1, int id=1){ push(l, r, id); if(l > j || r < i) return 0; if(i <= l && r <= j){ // cout << "interval " << l << ' ' << r << ' ' << t[id].sum << el; return t[id].sum; } int mid = (l+r)/2; return get_sum(i, j, l, mid, id*2) + get_sum(i, j, mid+1, r, id*2+1); } void get(int i, int j, vect<int>& aids, int l=1, int r=n-1, int id=1){ push(l, r, id); if(l > j || r < i) return; if(i <= l && r <= j){ aids.eb(id); return; } int mid = (l+r)/2; get(i, j, aids, l, mid, id*2); get(i, j, aids, mid+1, r, id*2+1); } int query(int l, int r){ vect<int> aids; get(l, r, aids); int ans = 0; for(int i=0;aids.size()>i;i++){ int id1 = aids[i]; node tmp = t[id1]; ans = max(ans, tmp.mx); for(int j=i+1;aids.size()>j;j++){ int id2 = aids[j]; tmp = tmp + t[id2]; ans = max(ans, tmp.mx); } } return ans+1; } }; void sol(){ cin >> n >> q; for(int i=0;n>i;i++) cin >> a[i]; if(n == 1){ while(q--){ int t, l, r, S, C; cin >> t >> l >> r; l--;r--; if(t == 1) cin >> S >> C, a[l] += S; else if(t == 2) cin >> S >> C, a[l] = S; else cout << 1 << el; } return; } for(int i=1;n>i;i++){ d[i] = a[i] - a[i-1]; } Seggs sgt; int a0 = a[0]; // cout << q << el; // deb; auto get_single_element = [&](int i){ if(i == 0) return a0; // cout << sgt.get_sum(1, i) + a << el; return sgt.get_sum(1, i) + a0; }; while(q--){ int t, l, r, S, C; cin >> t >> l >> r; l--;r--; if(t == 1) { cin >> S >> C; if(l == 0) a0 += S; if(l+1 <= r) sgt.add(l+1, r, C); if(l > 0) sgt.add(l, l, S); if(r+1 < n) sgt.add(r+1, r+1, -(S + C * (r-l))); }else if(t == 2){ cin >> S >> C; int al = sgt.get_sum(1, l) + a0, ar = r<n ? sgt.get_sum(1, r) + a0 : -69; if(l == 0) a0 = S; if(l > 0) sgt.add(l, l, -al + S); if(r+1<n) sgt.add(r+1, r+1, +ar - (S + C * (r-l))); if(l+1 <= r) sgt.assign(l+1, r, C); }else{ cout << sgt.query(l+1, r) << el; } // for(int i=0;n>i;i++) cout << get_single_element(i) << ' ';nextl; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); IO(); int t = 1; // cin >> t; while(t--) sol(); } /* ...-%%%%%%%%%%%... .:**#%=%%%%%+........-%%%%. . .%%%%%%=-..%#. .#%%. %%%+.. .: *%%. .%%. :. :%%%%%:. .%%. ... .: :: .=%%%. ..%%. #%#:%. : :.. =%%. %%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%.. .%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%. .%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%. =%%%...-%%%:::*%********%:::%%%****%::::::::%% .%- .%::::%%***%=:%%**********%%********%:::::::=%-:. .%.. #%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%. .%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%. .%%#%+%%***************##*+=+*==********************%%.:. .%% .%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%. .#%#*********************%%**************++************%%::::::%* .%%%. .%%***************#*****%%%****************************%%::::::%% .-%%%. .#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%. .%%**************#**%%%----%********%%**************#***#%%%#**%#******%* .%%**************#%%%--.....%%*******%%**************#**********#%******%%. .%%*************%%...........%%******%-%*************#***********%%*****%%. .%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%# .%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%% .#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%. .%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%. .+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%- ..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%. .%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%. .%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%. .%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%. ..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%. .%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%. ..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%.. -%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%. .%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%. .%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%. .+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%: =%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%% .%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%% *%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%% .%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%* %%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%. %%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%. .%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%.. :%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% . *%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*.. .%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . ..... %%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%. ..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%# .-%%+. ... .%%%%%%%:. */

Progression.cpp: In function 'void IO()':
Progression.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(FILE".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen(FILE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(FILE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(FILE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~