estimate_error @ 2024-11-20 21:34:45
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls p << 1
#define rs p << 1 | 1
ll n,m,q;
ll a[1000005];
struct edge{
ll maxn,tag1,vis,tag2;
}t[4000005];
void build(ll p,ll l,ll r){
if(l==r){
t[p].maxn=a[l];
return ;
}
ll mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
void push_down(ll p){
if(t[p].vis){
t[ls].tag1=t[p].tag1;
t[rs].tag1=t[p].tag1;
t[ls].vis=t[p].vis;
t[rs].vis=t[p].vis;
t[rs].maxn=t[p].tag1;
t[ls].maxn=t[p].tag1;
}else{
t[ls].tag2+=t[p].tag2;
t[rs].tag2+=t[p].tag2;
t[ls].maxn+=t[p].tag2;
t[rs].maxn+=t[p].tag2;
t[p].tag2=0;
}
}
void update1(ll p,ll l,ll r,ll tl,ll tr,ll k){
if(tl<=l&&r<=tr){
t[p].vis=1;
t[p].maxn=k;
t[p].tag1=k;
t[p].tag2=0;
return ;
}
push_down(p);
ll mid=(l+r)>>1;
if(tl<=mid)
update1(ls,l,mid,tl,tr,k);
if(mid<tr)
update1(rs,mid+1,r,tl,tr,k);
if(t[p].vis)
t[p].tag1=max(t[ls].tag1,t[rs].tag1);
else
t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
void update2(ll p,ll l,ll r,ll tl,ll tr,ll k){
if(tl<=l&&r<=tr){
if(t[p].vis)
t[p].tag1+=k;
t[p].tag2+=k;
t[p].maxn+=k;
return ;
}
push_down(p);
ll mid=(l+r)>>1;
if(tl<=mid)
update2(ls,l,mid,tl,tr,k);
if(mid<tr)
update2(rs,mid+1,r,tl,tr,k);
if(t[p].vis)
t[p].tag1=max(t[ls].tag1,t[rs].tag1);
else
t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
ll query(ll p,ll l,ll r,ll tl,ll tr){
if(tl<=l&&r<=tr){
if(t[p].vis)
return t[p].tag1;
return t[p].maxn;
}
ll res=-1145141919;
ll mid=(l+r)>>1;
push_down(p);
if(tl<=mid)
res=max(res,query(ls,l,mid,tl,tr));
if(mid<tr)
res=max(res,query(rs,mid+1,r,tl,tr));
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(q--){
ll opt;
cin>>opt;
if(opt==1){
ll l,r,x;
cin>>l>>r>>x;
update1(1,1,n,l,r,x);
}else if(opt==2){
ll l,r,x;
cin>>l>>r>>x;
update2(1,1,n,l,r,x);
}else{
ll l,r;
cin>>l>>r;
cout<<query(1,1,n,l,r)<<"\n";
}
}
return 0;
}
/*
4 2
10 4 -3 -7
1 1 3 0
3 1 1
*/by lct201714 @ 2024-11-20 21:45:22
push_down() 里面应该是有标记就传 if() else的写法是不对的
if（t[u].vis){
// do replace
}
if(t[u].add){
// do plus
}像这样分别传才行
by estimate_error @ 2024-11-20 21:54:39
@lct201714dalao改了一下但还是不太会 救一下
void push_down(ll p){
if(t[p].vis){
t[ls].tag1=t[p].tag1;
t[rs].tag1=t[p].tag1;
t[ls].vis=t[p].vis;
t[rs].vis=t[p].vis;
}
if(t[p].tag2){
t[ls].tag2+=t[p].tag2;
t[rs].tag2+=t[p].tag2;
t[ls].maxn+=t[p].tag2;
t[rs].maxn+=t[p].tag2;
t[p].tag2=0;
}
}by lct201714 @ 2024-11-20 22:06:48
下传之后要清空
下面是个人书写习惯，码风不大一样
// 优先下传覆盖标记的话, 在下传的时候要记得清空加标记
void rep(int u,int x){
t[u].vis=1; t[u].max=t[u].tag1=x; t[u].tag2=0;
}
void add(int u,int x){
t[u].tag2+=x; t[u].max+=x;
}
void push_down(int u){
if(t[u].vis){
rep(ls,t[u].tag1); rep(rs,t[u].tag1);
t[u].vis=0;
}
if(t[u].tag2){
add(ls,t[u].tag2); add(rs,t[u].tag2);
t[u].tag2=0;
}
我习惯把给左右儿子改变的函数放外面，你看看能不能理解。
by estimate_error @ 2024-11-20 22:16:11
@lct201714dalao又改了一下 好像还有点不对
void push_down(ll p){
if(t[p].vis){
t[ls].tag1=t[ls].maxn=t[p].tag1;
t[rs].tag1=t[rs].maxn=t[p].tag1;
t[ls].vis=1;
t[rs].vis=1;
t[ls].tag2=0;
t[rs].tag2=0;
t[p].vis=0;
}
if(t[p].tag2){
t[ls].tag2+=t[p].tag2;
t[rs].tag2+=t[p].tag2;
t[ls].maxn+=t[p].tag2;
t[rs].maxn+=t[p].tag2;
t[p].tag2=0;
}
}by lct201714 @ 2024-11-20 22:23:46
update函数里面走到完全覆盖的区间里面的变化也是要改的。
by lct201714 @ 2024-11-20 22:27:15
if(t[p].vis)
t[p].tag1=max(t[ls].tag1,t[rs].tag1);
else
t[p].maxn=max(t[ls].maxn,t[rs].maxn);
这个pushup也不太对
应该只需要
t[p].maxn=max(t[ls].maxn,t[rs].maxn;by estimate_error @ 2024-11-21 17:05:42
@lct201714em 对不起dalao update要改的是什么呢
by lct201714 @ 2024-11-21 17:19:44
if(tl<=l&&r<=tr){
t[p].vis=1;
t[p].maxn=k;
t[p].tag1=k;
t[p].tag2=0;
return ;
}
if(tl<=l&&r<=tr){
if(t[p].vis)
t[p].tag1+=k;
t[p].tag2+=k;
t[p].maxn+=k;
return ;
}这两部分应该和push_down()里面的修改是一致的。
by estimate_error @ 2024-11-21 17:24:27
@lct201714请问下我现在的修改和push down 差在哪里呢
by lct201714 @ 2024-11-21 17:40:49
if（t[p].vis) 的特判是不需要的。