SNXL @ 2024-07-27 17:03:36
#include <bits/stdc++.h>
using namespace std;
static char outlen = 2;
static bool outflag = false;
struct FastIO {
inline FastIO& operator >> (register int &f) {
f=0;
register char ch = getchar(), cmp = 0;
while(ch <= 32) {
ch = getchar();
}
cmp |= (ch == '-');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
f = (f << 3) + (f << 1) + (ch ^ 48);
ch = getchar();
}
return f = cmp ? -f : f, *this;
}
inline FastIO& operator >> (register long long &f) {
f = 0;
register char ch = getchar(), cmp = 0;
while(ch <= 32) {
ch = getchar();
}
cmp |= (ch == '-');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
f = (f << 3) + (f << 1) + (ch ^ 48);
ch = getchar();
}
return f = cmp ? -f : f, *this;
}
inline FastIO& operator >> (register char &f) {
return f = getchar(), *this;
}
inline FastIO& operator >> (register string &f) {
f.clear();
register char ch = getchar();
while(ch != '\n' && ch != ' ') {
f.push_back(ch);
ch = getchar();
}
return *this;
}
inline FastIO& operator >> (register double &f) {
f = 0;
register char ch = getchar(), cmp = 0;
register long long ff = 0;
register long long x = 0;
register double d = 0.1;
while(ch <= 32) {
ch = getchar();
}
cmp |= (ch == '-');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
ff = (ff << 3) + (ff << 1) + (ch ^ 48);
ch = getchar();
}
f += cmp ? -(double)ff : (double)ff;
cmp |= (ch == '.');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 3) + (x << 1) + (ch ^ 48);
d *= 0.1;
ch = getchar();
}
f += x * d;
return *this;
}
inline FastIO& operator >> (register float &f) {
f = 0;
register char ch = getchar(), cmp = 0;
register int ff = 0;
register float d = 0.1, x = 0;
while(ch <= 32) {
ch = getchar();
}
cmp |= (ch == '-');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
ff = (ff << 3) + (ff << 1) + (ch ^ 48);
ch = getchar();
}
f += cmp ? -(float)ff : (float)ff;
cmp |= (ch == '.');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
x += (ch - 48) * d;
d *= 0.1;
ch = getchar();
}
f += x;
return *this;
}
inline FastIO& operator >> (register short &f) {
f = 0;
register char ch = getchar(), cmp = 0;
while(ch <= 32) {
ch = getchar();
}
cmp |= (ch == '-');
if(cmp) {
ch = getchar();
}
while(isdigit(ch)) {
f = (f << 3) + (f << 1) + (ch ^ 48);
ch = getchar();
}
return f = cmp ? -f : f, *this;
}
inline FastIO& operator << (register int f) {
static char cc[10], len = -1;
!f ? putchar('0') : 0;
f < 0 ? putchar('-'), f = -f : 0;
while(f) {
cc[++ len] = f % 10 + 48;
f /= 10;
}
while(~len) {
putchar(cc[len]);
-- len;
}
return *this;
}
inline FastIO& operator << (register long long f) {
static char cc[25], len = -1;
!f ? putchar('0') : 0;
f < 0 ? putchar('-'), f = -f : 0;
while(f) {
cc[++ len] = f % 10 + 48;
f /= 10;
}
while(~len) {
putchar(cc[len]);
-- len;
}
return *this;
}
inline FastIO& operator << (register char f) {
return putchar(f), *this;
}
inline FastIO& operator << (register string f) {
register int nn = f.size();
for(register int i = 0; i < nn; ++ i) {
putchar(f[i]);
}
return *this;
}
inline FastIO& operator << (register double f) {
register int y = int(f);
register char cnt = 0;
*this << y;
f -= y;
if(outflag) {
while(f - int(f) > 1e-6 && ++ cnt <= outlen) {
f *= 10;
}
} else {
while(f - int(f) > 1e-6) {
f *= 10;
}
}
if(f) {
*this << '.' << int(f);
}
return *this;
}
inline void setprecision (register char len) {
outlen = len;
outflag = true;
return;
}
};
FastIO io;
#define cin io
#define cout io
#define endl '\n'
#define int long long
const int N=1e6+10;
int n, m;
int sum[N << 2], a[N];
int lazy[N << 2];
int p;
int l, r, x;
int b[N << 2];
int cover[N << 2];
void push_up(int pos) {
sum[pos] = max (sum[pos << 1], sum[pos << 1|1]);
}
void push_down(int pos, int l, int r) {
if(b[pos]) {
sum[pos << 1] = sum[pos << 1|1] = cover[pos];
cover[pos << 1] = cover[pos << 1|1] = cover[pos];
lazy[pos << 1] = lazy[pos << 1|1] = lazy[pos];
lazy[pos] = cover[pos] = b[pos] = 0;
b[pos << 1] = b[pos << 1|1] = 1;
}
if(lazy[pos]) {
lazy[pos << 1] += lazy[pos];
lazy[pos << 1|1] += lazy[pos];
sum[pos << 1] += lazy[pos];
sum[pos << 1|1] += lazy[pos];
lazy[pos] = 0;
}
}
void build(int pos, int l, int r) {
if (l == r) {
sum[pos] = a[l];
return;
}
int mid = l+r >> 1;
build(pos << 1, l, mid);
build(pos << 1|1, mid+1, r);
push_up(pos);
}
void add(int pos, int l, int r, int x, int y, int num) {
if (x <= l && y >= r) {
lazy[pos] += num;
sum[pos] += num;
return;
}
push_down(pos, l, r);
int mid = l+r >> 1;
if (x <= mid) {
add(pos << 1, l, mid, x, y, num);
}
if (y > mid) {
add(pos << 1|1, mid+1, r, x, y, num);
}
push_up(pos);
}
int find(int pos, int l, int r, int x, int y) {
if (x <= l && y >= r) {
return sum[pos];
}
push_down(pos, l, r);
int mid = l+r >> 1;
int ans=LLONG_MIN;
if (x <= mid) {
ans = max (ans, find(pos << 1, l, mid, x, y));
}
if (y>mid) {
ans = max (ans, find(pos << 1|1, mid+1, r, x, y));
}
return ans;
}
void update(int pos, int l, int r, int x, int y, int num) {
if (x <= l && y >= r) {
sum[pos] = num;
lazy[pos] = 0;
cover[pos] = num;
b[pos] = 1;
return;
}
push_down(pos, l, r);
int mid = l+r >> 1;
if (x <= mid) {
update (pos << 1, l, mid, x, y, num);
}
if (y>mid) {
update (pos << 1|1, mid+1, r, x, y, num);
}
push_up(pos);
}
signed main() {
cin >> n >> m;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (m--) {
cin >> p;
if (p == 1) {
cin >> l >> r >> x;
update (1, 1, n, l, r, x);
}
if (p == 2) {
cin >> l >> r >> x;
add (1, 1, n, l, r, x);
}
if (p == 3) {
cin >> l >> r;
cout << find (1, 1, n, l, r) << '\n';
}
}
return 0;
}