INTP_A @ 2024-11-26 20:54:45
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,maxn=-1e18-1,a[2000010];
struct node{
int sum,add;
bool g=false;
}c[8000010];
void pushup(int k){
c[k].sum=max(c[k<<1].sum,c[k<<1|1].sum);
return;
}
void build(int k,int l,int r){
if(l==r){
c[k].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
return;
}
void pushdown(int k){
if(c[k].g){
c[k].add=0;
c[k].g=0;
c[k<<1].add=0;
c[k<<1].sum=c[k].sum;
c[k<<1].g=true;
c[k<<1|1].add=0;
c[k<<1|1].sum=c[k].sum;
c[k<<1|1].g=true;
return;
}
c[k<<1].add+=c[k].add;
c[k<<1].sum+=c[k].add;
c[k<<1|1].add+=c[k].add;
c[k<<1|1].sum+=c[k].add;
c[k].add=0;
pushup(k);
return;
}
void ope1(int k,int l,int r,int x,int y,int ll){
if(l>y||r<x)return;
if(l>=x&&r<=y){
c[k].add+=ll;
c[k].sum+=ll;
return;
}
pushdown(k);
int mid=(l+r)>>1;
ope1(k<<1,l,mid,x,y,ll);
ope1(k<<1|1,mid+1,r,x,y,ll);
pushup(k);
return;
}
void ope2(int k,int l,int r,int x,int y,int oo){
if(l>y||r<x)return;
if(l>=x&&r<=y){
c[k].add=0;
c[k].sum=oo;
c[k].g=true;
return;
}
pushdown(k);
int mid=(l+r)>>1;
ope2(k<<1,l,mid,x,y,oo);
ope2(k<<1|1,mid+1,r,x,y,oo);
pushup(k);
return;
}
void chaxun(int k,int l,int r,int x,int y){
if(l>y||r<x)return;
if(l>=x&&r<=y){
maxn=max(maxn,c[k].sum);
return;
}
int mid=(l+r)>>1;
chaxun(k<<1,l,mid,x,y);
chaxun(k<<1|1,mid+1,r,x,y);
return;
}
signed main(){
cin>>n>>m;
int op,l,r,x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
cin>>op;
if(op==1){
cin>>l>>r>>x;
ope2(1,1,n,l,r,x);
}else if(op==2){
cin>>l>>r>>x;
ope1(1,1,n,l,r,x);
}else{
cin>>l>>r;
chaxun(1,1,n,l,r);
cout<<maxn<<endl;
maxn=-1e18-1;
}
}
return 0;
}
20分真的调不出来了
by zzz13579zzz @ 2024-11-26 20:59:10
区间修改为什么
by wjr_jok @ 2024-11-26 21:04:50
@INTP_A 对啊你改的是个区间欸
by INTP_A @ 2024-11-26 21:43:52
因为sum里存的是区间最大值啊,如果把整个区间修改,不就相当于修改值就是最大值吗@wjr_jok@zzz13579zzz
by wjr_jok @ 2024-11-26 21:45:03
@INTP_A 所以记录加法的是
by zzz13579zzz @ 2024-11-26 21:51:58
push_down里面不用清空加标记,不然下传不了@@INTP_A
by zzz13579zzz @ 2024-11-26 21:52:47
就是下传修改标记的时候
by wjr_jok @ 2024-11-26 22:01:53
wc什么四不像线段树啊
by INTP_A @ 2024-11-27 15:12:17
@wjr_jok 刚学线段树写的确实抽象QWQ
by INTP_A @ 2024-11-27 15:20:27
才看到查询函数没写pushdown,此贴已结。谢谢两位大佬