yjy_echo @ 2024-06-29 13:44:49
#include<bits/stdc++.h>
#define ls(p) p<<1
#define rs(p) p<<1|1
#define ll long long
#define mid (t[u].l+t[u].r)/2
using namespace std;
const int N=1e6+10;
ll n,m,a,b,c,d,ans[N];
struct tree{
ll l,r,sum,mul,add;
}t[N*4];
void pushup(ll u){
t[u].sum=max(t[ls(u)].sum,t[rs(u)].sum);
}
void build(ll u,ll l,ll r){
t[u].mul=LLONG_MIN;
t[u].l=l,t[u].r=r;
if(l==r){
t[u].sum=ans[l];
return ;
}
build(ls(u),l,mid);
build(rs(u),mid+1,r);
pushup(u);
}
void pushdown(ll u){
if(!t[u].add&&t[u].mul==LLONG_MIN) return ;
if(t[u].mul!=LLONG_MIN){
t[ls(u)].mul+=t[u].mul;
t[rs(u)].mul+=t[u].mul;
t[ls(u)].sum=t[u].mul;
t[rs(u)].sum=t[u].mul;
t[u].mul=LLONG_MIN;
t[u].add=0;
}
if(t[u].add){
t[ls(u)].add+=t[u].add;
t[rs(u)].add+=t[u].add;
t[ls(u)].sum+=t[u].add;
t[rs(u)].sum+=t[u].add;
t[u].add=0;
}
}
void update_add(ll u,ll l,ll r,ll k){
if(t[u].r==0||t[u].l==0) return;
if(l<=t[u].l&&t[u].r<=r){
t[u].add+=k;
t[u].sum+=k;
//cout<<u<<' '<<t[u].l<<' '<<t[u].r<<' '<<t[u].sum<<endl;
return ;
}
pushdown(u);
if(l<=mid) update_add(ls(u),l,r,k);
if(r>mid) update_add(rs(u),l,r,k);
pushup(u);
}
void update_mul(ll u,ll l,ll r,ll k){
if(t[u].r==0||t[u].l==0) return;
if(l<=t[u].l&&t[u].r<=r){
t[u].mul=k;
t[u].sum=k;
//cout<<u<<' '<<t[u].l<<' '<<t[u].r<<' '<<t[u].sum<<endl;
return ;
}
pushdown(u);
if(l<=mid) update_mul(ls(u),l,r,k);
if(r>mid) update_mul(rs(u),l,r,k);
pushup(u);
}
ll query(ll u,ll l,ll r){
ll res=LLONG_MIN;
if(t[u].l>r||t[u].r<l) return 0;
if(t[u].l>=l&&t[u].r<=r) return t[u].sum;
pushdown(u);
if(l<=mid) res=max(res,query(ls(u),l,r));
if(r>mid) res=max(res,query(rs(u),l,r));
return res;
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%lld",&ans[i]);
build(1,1,n);
while(m--){
scanf("%lld",&a);
if(a==1){
scanf("%lld%lld%lld",&b,&c,&d);
update_mul(1,b,c,d);
}
else if(a==2){
scanf("%lld%lld%lld",&b,&c,&d);
update_add(1,b,c,d);
}
else if(a==3){
scanf("%lld%lld",&b,&c);
printf("%lld\n",query(1,b,c));
}
}
return 0;
}by 123huchenghao @ 2024-06-29 18:01:18
#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int N=1e6+10;
const int INF=1e16;
struct node{
int max;
int add;
int lazy;
}tree[N*16];
int n,m,a[N];
void pushup(int p){
tree[p].max=max(tree[ls].max,tree[rs].max);
return;
}
void pushdown(int p){
if(tree[p].lazy!=-INF){
tree[ls].lazy=tree[rs].lazy=tree[p].lazy;
tree[ls].max=tree[rs].max=tree[p].lazy;
tree[ls].add=tree[rs].add=0;
tree[p].lazy=-INF;
}
if(tree[p].add){
tree[ls].add+=tree[p].add;
tree[rs].add+=tree[p].add;
tree[ls].max+=tree[p].add;
tree[rs].max+=tree[p].add;
tree[p].add=0;
}
}
void build(int p,int l,int r){
tree[p].lazy=-INF;
if(l==r){tree[p].max=a[l];return;}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void upd1(int p,int l,int r,int x,int y,int k){
if(x<=l&&y>=r){
tree[p].max=k;
tree[p].lazy=k;
tree[p].add=0;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) upd1(ls,l,mid,x,y,k);
if(y>mid) upd1(rs,mid+1,r,x,y,k);
pushup(p);
}
void upd2(int p,int l,int r,int x,int y,int k){
if(x<=l&&y>=r){
tree[p].max+=k;
tree[p].add+=k;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) upd2(ls,l,mid,x,y,k);
if(y>mid) upd2(rs,mid+1,r,x,y,k);
pushup(p);
}
int query(int p,int l,int r,int x,int y){
int res=-INF;
if(x<=l&&y>=r){
res=max(res,tree[p].max);
return res;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) res=max(res,query(ls,l,mid,x,y));
if(y>mid) res=max(res,query(rs,mid+1,r,x,y));
return res;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
for(int i=1;i<=m;++i){
int op=read();
if(op==1){
int l,r,x;
l=read();r=read();x=read();
upd1(1,1,n,l,r,x);
}
else if(op==2){
int l,r,x;
l=read();r=read();x=read();
upd2(1,1,n,l,r,x);
}
else{
int l,r;
l=read();r=read();
printf("%lld\n",query(1,1,n,l,r));
}
}
return 0;
}by Fish_Love_Water @ 2024-06-29 21:10:17
@123huchenghao ？