gmx0424 @ 2023-11-01 23:22:04
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1e11;
int n, q;
const int maxn = 1e6 + 5;
ll a[maxn], val[maxn << 2], add[maxn << 2], re[maxn << 2];
bool flag[maxn << 2];//标记是否要修改
inline int read() {
int ans=0,op=1;
char c = getchar();
while(c<'0'|| c>'9') {
if (c == '-'){
op = -1;
}
c=getchar();
}
while(c>='0'&& c<='9'){
ans = ans * 10 + c - '0';
c=getchar();
}
return ans * op;
}
void pushdown(int rt){
if (flag[rt] ){
flag[rt<<1] = true; //修改标记
flag[rt<<1|1] = true;
add[rt<<1] = 0;//修改加法-子节点清空
add[rt<<1|1] = 0;
re[rt<<1] = re[rt];//修改覆盖
re[rt<<1|1] = re[rt];
val[rt<<1] = re[rt];//修改最大值
val[rt<<1|1] = re[rt];
flag[rt] = false;
}
if (add[rt]) {
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
val[rt<<1] += add[rt];
val[rt<<1|1] += add[rt];
add[rt] = 0;
}
}
void pushup(int rt){
val[rt] == max (val[rt << 1] ,val[rt << 1 | 1] );
}
void build (int rt, int l, int r){
flag[rt] = false;
add[rt] = 0;
if (l == r) {
val[rt] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void rev(int rt, int l, int r, int ql, int qr, ll k){
if (qr < l || ql > r){
return ;
}
if (ql <= l && r <= qr){
re[rt] = k;
add[rt] = 0;
val[rt] = k;
flag[rt] = true;
return ;
}
pushdown(rt);
int mid = (l + r)>>1;
rev(rt<<1,l,mid,ql,qr,k);
rev(rt<<1|1,mid+1,r,ql,qr,k);
pushup(rt);
}
void update(int rt, int l, int r, int ql, int qr, ll k){
if (qr < l || ql > r){
return ;
}
if (ql <= l && r <= qr){
add[rt] += k;
val[rt] += k;
return ;
}
pushdown(rt);
int mid = (l + r)>>1;
update(rt<<1,l,mid,ql,qr,k);
update(rt<<1|1,mid+1,r,ql,qr,k);
pushup(rt);
}
ll ask(int rt, int l, int r, int ql, int qr){
if (qr<l||ql>r){
return 0;
}
if(ql<=l&&r<=qr){
return val[rt];
}
pushdown(rt);
int mid = (l+r)>>1;
ll res = -INF;
res = max(res,ask(rt<<1,l,mid,ql,qr));
res = max(res,ask(rt<<1|1,mid+1,r,ql,qr));
return res;
}
int main () {
n=read(), q=read();
for (int i = 1; i <= n; i++){
a[i] = read();
}
build(1,1,n);
while (q--){
int op ;
op=read();
if(op == 1){
int l, r;
ll x;
l=read();
r=read();
x=read();
rev(1,1,n,l,r,x);//修改
}else if(op==2){
int l, r;
ll x;
l=read();
r=read();
x=read();
update(1,1,n,l,r,x);
}else {
int l, r;
l=read();
r=read();
cout << ask(1,1,n,l,r)<<'\n';
}
}
return 0;
}