线段树,RE+WA求助

P1253 扶苏的问题

luqyou @ 2023-01-09 14:49:35

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=2147483647;
const int N=1e6+10;
int n,m;
ll c[N];
struct node{
    int l,r;
    ll v,tag_add,tag_rev;
}a[4*N];
int ls(int u){
    return u<<1;
}
int rs(int u){
    return (u<<1)|1;
}
bool inrange(int L,int R,int l,int r){
    return (L<=l)&&(r<=R);
}
bool outofrange(int L,int R,int l,int r){
    return (R<l)||(r<L);
}
void build(int l,int r,int u){
    if(l!=r){
        int mid=(l+r)>>1;
        build(l,mid,ls(u));
        build(mid+1,r,rs(u));
        a[u]=(node){l,r,max(a[ls(u)].v,a[rs(u)].v),0,inf};
    }
    else{
        a[u]=(node){l,r,c[l],0,inf};
    }
}
void pushup(int u){
    a[u].v=max(a[ls(u)].v,a[rs(u)].v);
}
void pushdown(int u){
    int L=a[u].l,R=a[u].r;
    if(L==R) return ;
    if(a[u].tag_rev!=inf){
        a[ls(u)].tag_add=0;
        a[ls(u)].tag_rev=a[u].tag_rev;
        a[rs(u)].tag_add=0;
        a[rs(u)].tag_rev=a[u].tag_rev;
        a[ls(u)].v=a[u].tag_rev;
        a[rs(u)].v=a[u].tag_rev;
        a[u].tag_rev=inf;
    }
    a[ls(u)].tag_add+=a[u].tag_add;
    a[rs(u)].tag_add+=a[u].tag_add;
    a[ls(u)].v+=a[u].tag_add;
    a[rs(u)].v+=a[u].tag_add; 
    a[u].tag_add=0;
}
void mkt_add(int l,int r,int u,ll k){
    int L=a[u].l,R=a[u].r;
    if(a[u].tag_add||a[u].tag_rev!=inf) pushdown(u);
    if(inrange(l,r,L,R)){
        a[u].tag_add+=k;
        a[u].v+=k;
        pushdown(u);
    }
    else if(!outofrange(l,r,L,R)){
        mkt_add(l,r,ls(u),k);
        mkt_add(l,r,rs(u),k);
    }
    else return ;
}
void mkt_rev(int l,int r,int u,ll k){
    int L=a[u].l,R=a[u].r;
    if(a[u].tag_add||a[u].tag_rev!=inf) pushdown(u);
    if(inrange(l,r,L,R)){
        a[u].tag_rev=k;
        a[u].v=k;
        pushdown(k);
    }
    else if(!outofrange(l,r,L,R)){
        mkt_rev(l,r,ls(u),k);
        mkt_rev(l,r,rs(u),k);
    }
    else return ;
}
ll search(int l,int r,int u){
    int L=a[u].l,R=a[u].r;
    if(a[u].tag_add||a[u].tag_rev!=inf) pushdown(u);
    if(inrange(l,r,L,R)){
        return a[u].v;
    }
    else if(!outofrange(l,r,L,R)){
        return max(search(l,r,ls(u)),search(l,r,rs(u)));
    }
    else return -inf;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            ll x;
            cin>>l>>r>>x;
            mkt_rev(l,r,1,x);
        } 
        if(op==2){
            int l,r;
            ll x;
            cin>>l>>r>>x;
            mkt_add(l,r,1,x);
        }
        if(op==3){
            int l,r;
            cin>>l>>r;
            cout<<search(l,r,1)<<endl;
        }
    }
    return 0;
}

|