20 分线段树求助

Fast_IO @ 2022-04-15 17:21:20

#include<iostream>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
const int N = 1e6+5;
struct Node{int l,r,v,lazy_tag1,lazy_tag2;}tr[4*N];
int a[N],q,n;
inline void pushup(int p){
    tr[p].v=max(tr[p*2].v,tr[p*2+1].v);
}
inline void bulid(int p,int l,int r){
    int mid=l+r>>1;
    tr[p].l=l;
    tr[p].r=r;
    if(l==r){
        tr[p].v=a[l];
        return ;
    }
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    pushup(p);
} 
inline void pushdown(int p){
    tr[p*2].lazy_tag1+=tr[p].lazy_tag1,tr[p*2].v+=tr[p].lazy_tag1; 
    tr[p*2+1].lazy_tag1+=tr[p].lazy_tag1,tr[p*2+1].v+=tr[p].lazy_tag1; 
    tr[p].lazy_tag1=0;
    if(tr[p].lazy_tag2!=INF){
        tr[p*2].v=tr[p*2].lazy_tag2=tr[p].lazy_tag2,tr[p*2].lazy_tag1=0;
        tr[p*2+1].v=tr[p*2+1].lazy_tag2=tr[p].lazy_tag2,tr[p*2+1].lazy_tag1=0;
        tr[p].lazy_tag2=INF;
    }
}
inline int query(int p,int ql,int qr){
    if(ql<=tr[p].l && qr>=tr[p].r) return tr[p].v;
    int mid=tr[p].l+tr[p].r>>1;
    pushdown(p);
    if(qr<=mid) return query(p*2,ql,qr);
    else if(ql>mid) return query(p*2+1,ql,qr);
    else return max(query(p*2,ql,qr),query(p*2+1,ql,qr));
}
inline void update(int p,int ul,int ur,int d){
    if(ul<=tr[p].l && ur>=tr[p].r){
        tr[p].lazy_tag1+=d;
        tr[p].v+=d;
        return ;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(ur<=mid){
        update(p*2,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }else if(ul>mid){
        update(p*2+1,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }else{
        update(p*2,ul,ur,d);
        update(p*2+1,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }
    pushup(p);
}
inline void update2(int p,int ul,int ur,int d){
    if(ul<=tr[p].l && ur>=tr[p].r){
        tr[p].v=tr[p].lazy_tag2=d;
        tr[p].lazy_tag1=0;
        return ;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(ur<=mid){
        update2(p*2,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }else if(ul>mid){
        update2(p*2+1,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }else{
        update2(p*2,ul,ur,d);
        update2(p*2+1,ul,ur,d);
        tr[p].v=max(tr[2*p].v,tr[2*p+1].v);
    }
    pushup(p);
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    bulid(1,1,n);
    while(q--){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==3) cout<<query(1,l,r)<<endl;
        else if(op==2){
            cin>>x;
            update(1,l,r,x);
        }else{
            cin>>x;
            update2(1,l,r,x);
        }
    } 
    return 0;
}

by Fast_IO @ 2022-04-15 18:00:17

@StillEmpty 我 INF 开小了，应该是这个的问题。

by StillEmpty @ 2022-04-15 18:04:32

@Fast_IO 又给你改对一个问题。https://www.luogu.com.cn/record/73958242

if(ul<=tr[p].l && ur>=tr[p].r){
        tr[p].v+=d;
        if(tr[p].lazy_tag2 != INF) tr[p].lazy_tag2+=d;
        else tr[p].lazy_tag1+=d;
        return ;
    }

你看是不是

by Fast_IO @ 2022-04-15 18:06:09

@StillEmpty 应该是

by StillEmpty @ 2022-04-15 18:27:33

@Fast_IO 帮你改对了。push_down同理改就好了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1000000000000;
const int N = 1e6+5;
struct Node{int l,r,v,lazy_tag1,lazy_tag2;}tr[4*N];
int a[N],q,n;
inline void pushup(int p){
    tr[p].v=max(tr[p*2].v,tr[p*2+1].v);
}
 void bulid(int p,int l,int r){
    int mid=l+r>>1;
    tr[p].l=l;
    tr[p].r=r;tr[p].lazy_tag2 = INF;
    if(l==r){
        tr[p].v=a[l];
        return ;
    }
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    pushup(p);
} 
inline void pushdown(int p){
    tr[p*2].v+=tr[p].lazy_tag1; 
    if(tr[p*2].lazy_tag2 != INF) tr[p*2].lazy_tag2+=tr[p].lazy_tag1;
    else tr[p*2].lazy_tag1+=tr[p].lazy_tag1;
    tr[p*2+1].v+=tr[p].lazy_tag1; 
    if(tr[p*2+1].lazy_tag2 != INF) tr[p*2+1].lazy_tag2+=tr[p].lazy_tag1;
    else tr[p*2+1].lazy_tag1+=tr[p].lazy_tag1;
    tr[p].lazy_tag1=0;
    if(tr[p].lazy_tag2!=INF){
        tr[p*2].v=tr[p*2].lazy_tag2=tr[p].lazy_tag2,tr[p*2].lazy_tag1=0;
        tr[p*2+1].v=tr[p*2+1].lazy_tag2=tr[p].lazy_tag2,tr[p*2+1].lazy_tag1=0;
        tr[p].lazy_tag2=INF;
    }
}
int query(int p,int ql,int qr){
    if(ql<=tr[p].l && qr>=tr[p].r) return tr[p].v;
    int mid=tr[p].l+tr[p].r>>1;
    pushdown(p);
    if(qr<=mid) return query(p*2,ql,qr);
    else if(ql>mid) return query(p*2+1,ql,qr);
    else return max(query(p*2,ql,qr),query(p*2+1,ql,qr));
}
void update(int p,int ul,int ur,int d){
    if(ul<=tr[p].l && ur>=tr[p].r){
        tr[p].v+=d;
        if(tr[p].lazy_tag2 != INF) tr[p].lazy_tag2+=d;
        else tr[p].lazy_tag1+=d;
        return ;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(ur<=mid){
        update(p*2,ul,ur,d);
    }else if(ul>mid){
        update(p*2+1,ul,ur,d);
    }else{
        update(p*2,ul,ur,d);
        update(p*2+1,ul,ur,d);
    }
    pushup(p);
}
void update2(int p,int ul,int ur,int d){
    if(ul<=tr[p].l && ur>=tr[p].r){
        tr[p].v=tr[p].lazy_tag2=d;
        tr[p].lazy_tag1=0;
        return ;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(ur<=mid){
        update2(p*2,ul,ur,d);
    }else if(ul>mid){
        update2(p*2+1,ul,ur,d);
    }else{
        update2(p*2,ul,ur,d);
        update2(p*2+1,ul,ur,d);
    }
    pushup(p);
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    bulid(1,1,n);
    while(q--){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==3) cout<<query(1,l,r)<<endl;
        else if(op==2){
            cin>>x;
            update(1,l,r,x);
        }else{
            cin>>x;
            update2(1,l,r,x);
        }
    } 
    return 0;
}

by Fast_IO @ 2022-04-15 18:27:47

@StillEmpty 谢谢大佬

by StillEmpty @ 2022-04-15 18:27:49

@Fast_IO 求关注qwq

by Fast_IO @ 2022-04-15 18:28:50

@StillEmpty 给您关注了

此贴终