20 pts AC #1 #3

fe117 @ 2024-07-09 20:26:08

by fe117 @ 2024-07-09 20:26:24

#include <iostream> 
#define ll long long
using namespace std;
struct jd{
    ll l,r,sum,tag=0,tag2=1;//tag是赋值，tag2是加 
    bool f1,f2;
    //bool iftag=0;
};
jd tr[800005]={};
ll a[100005]={};
void build(ll l,ll r,ll n){
    tr[n].l=l;
    tr[n].r=r;
    tr[n].f1=0,tr[n].f2=0;
    if(l==r){
        tr[n].sum=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build(l,mid,2*n);
    build(mid+1,r,2*n+1);
    tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
}
void downtag(int n){
    if(tr[n].f1+tr[n].f2==0){
        return;
    }
    if(tr[2*n].l==tr[2*n].r){
        if(tr[n].f2==0){
            tr[2*n].sum=tr[n].tag;
        }
        else{
            tr[2*n].sum+=tr[n].tag;
        }
    }
    else{
        if(tr[n].f2==0){
            tr[2*n].sum=tr[n].tag;
            tr[2*n].tag=tr[n].tag;
            tr[2*n].tag2=0; 
            tr[2*n].f1=1;
        }
        else{
            tr[2*n].sum+=tr[n].tag;
            if(tr[2*n].f1==1){
                tr[2*n].tag+=tr[n].tag;
            }
            else{
                tr[2*n].tag2+=tr[n].tag;
                tr[2*n].f2=1;
            }
        }
    }
    if(tr[2*n+1].l==tr[2*n+1].r){
        if(tr[n].f2==0){
            tr[2*n+1].sum=tr[n].tag;
        }
        else{
            tr[2*n+1].sum+=tr[n].tag;
        }
    }
    else{
        if(tr[n].f2==0){
            tr[2*n+1].sum=tr[n].tag;
            tr[2*n+1].tag=tr[n].tag;
            tr[2*n+1].tag2=0; 
            tr[2*n+1].f1=1;
        }
        else{
            tr[2*n+1].sum+=tr[n].tag;
            if(tr[2*n+1].f1==1){
                tr[2*n+1].tag+=tr[n].tag;
            }
            else{
                tr[2*n+1].tag2+=tr[n].tag;
                tr[2*n+1].f2=1;
            }
        }
    }
    tr[n].tag=0;
    tr[n].tag2=0;
    tr[n].f1=0;
    tr[n].f2=0;
    tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
}
void pushtag(ll l,ll r,ll n,ll tag){
    if(tr[n].l==tr[n].r){
        tr[n].sum=tag;
        return;
    }
    downtag(n);
    if(tr[2*n].r<l){
        pushtag(l,r,2*n+1,tag);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
        return;
    }
    if(tr[2*n].r>=r){
        pushtag(l,r,2*n,tag);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
        return;
    } 
    if(tr[n].l==l&&tr[n].r==r){
        tr[n].tag=tag;
        tr[n].tag2=0;
        tr[n].f1=1;
        tr[n].f2=0;
        tr[n].sum=tag;
        return;
    }
    pushtag(l,tr[2*n].r,2*n,tag);
    pushtag(tr[2*n+1].l,r,2*n+1,tag);
    tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
}
void pushtag2(ll l,ll r,ll n,ll tag){
    if(tr[n].l==tr[n].r){
        //if(tag==0)return;
        tr[n].sum+=tag;
        return;
    }
    downtag(n);
    if(tr[2*n].r<l){
        pushtag2(l,r,2*n+1,tag);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
        return;
    }
    if(tr[2*n].r>=r){
        pushtag2(l,r,2*n,tag);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
        return;
    } 
    if(tr[n].l==l&&tr[n].r==r){
        if(tr[n].f1==0){
            tr[n].tag2+=tag;
            tr[n].f2=1;
        }
        else{
            tr[n].tag+=tag;
        }
        tr[n].sum+=tag;
        return;
    }
    pushtag2(l,tr[2*n].r,2*n,tag);
    pushtag2(tr[2*n+1].l,r,2*n+1,tag);
    tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum);
}
ll getsum(ll l,ll r,ll n){
    if(tr[n].l==tr[n].r){
        return tr[n].sum;
    }
    /*if(tr[2*n].l==tr[2*n].r){
        tr[2*n].sum+=tr[n].tag;
    }*/
    downtag(n);
    int ret;
    if(tr[2*n].r<l){
        ret=getsum(l,r,2*n+1);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum); 
        return ret;
    }
    if(tr[2*n].r>=r){
        ret=getsum(l,r,2*n);
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum); 
        return ret;
    }
    if(tr[n].l==l&&tr[n].r==r){
        ret=tr[n].sum;
        tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum); 
        return ret;
    }
    ret=max(getsum(l,tr[2*n].r,2*n),getsum(tr[2*n+1].l,r,2*n+1));
    tr[n].sum=max(tr[2*n].sum,tr[2*n+1].sum); 
    return ret;
}
void print_tree(){
    for(int j=1;j<=1005;j++){
        if(tr[j].l==0)continue;
        cout<<j<<":"<<tr[j].l<<" to "<<tr[j].r;
        cout<<",tag:"<<tr[j].tag<<" tag2:";
        cout<<tr[j].tag2<<" sum:"<<tr[j].sum;
        cout<<".\n";
    }
}
int main(){
    //freopen("P1253_2.in","r",stdin);
    //freopen("P1253_2.ans","w",stdout);
    int n,m,p,x,y,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    //print_tree();
    for(int i=0;i<m;i++){
        cin>>p;
        if(p==1){
            cin>>x>>y>>k;
            pushtag(x,y,1,k);
        }
        else if(p==2){
            cin>>x>>y>>k;
            pushtag2(x,y,1,k);
        }
        else{
            cin>>x>>y;
            cout<<getsum(x,y,1)<<endl;
            /*if(x==2&&y==4){
                cout<<tr[1].tag<<"-"<<tr[1].sum;
            }*/
        }
        //print_tree();
    }
    //cout<<tr[8].r<<":"<<tr[1].sum<<endl;
    return 0;
}
/*
4 8
10 4 -3 -7
1 1 3 0
3 1 4
2 3 4 -4
3 1 4
3 1 4
1 2 4 -9
3 1 4
3 1 1
*/

by xiao_pai_sha_shou @ 2024-07-10 14:52:15

大佬解决问题了吗，蒟蒻遇到了同样的问题。

%%%

by AndyC @ 2024-07-18 10:39:24

同+1

by Emily666 @ 2024-07-18 20:44:39

同问QwQ

by kongdeqian @ 2024-07-19 10:03:45

同问

by zqh123b @ 2024-08-03 10:55:49

同问

回复请@

by zqh123b @ 2024-08-03 10:57:09

here有帮助吗？

验证码93jc祭