60pts求调

MornHus @ 2023-08-24 16:18:59

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1000003
ll tree[maxn<<2];
ll nul=1e18;
ll lazy_add[maxn<<2];
ll lazy_set[maxn<<2];
int n,q;
void pushup(int k){
    tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
void build(int k,int l,int r){
    lazy_set[k]=nul;
    if(l==r){
        cin>>tree[k];
    }else{
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }
}
void pushdown(int k){
    if(lazy_set[k]!=nul){
        tree[k<<1]=lazy_set[k];
        tree[k<<1|1]=lazy_set[k];
        lazy_add[k<<1]=lazy_add[k<<1|1]=0;
        lazy_set[k]=nul;
    }else if(lazy_add[k]){
        tree[k<<1]+=lazy_add[k];
        tree[k<<1|1]+=lazy_add[k];
        if(lazy_set[k<<1]!=nul){
            lazy_set[k<<1]+=lazy_add[k];
        }else{
            lazy_add[k<<1]+=lazy_add[k];
        }
        if(lazy_set[k<<1|1]!=nul){
            lazy_set[k<<1|1]+=lazy_add[k];
        }else{
            lazy_add[k<<1|1]+=lazy_add[k];
        }
        lazy_add[k]=0;
    }
}
void update(int option,int k,int l,int r,int L,int R,int val){
    if(L<=l&&r<=R){
        if(option==1){
            tree[k]=val;
            lazy_set[k]=val;
            lazy_add[k]=0;
        }else{
            tree[k]+=val;
            if(lazy_set[k]!=nul){
                lazy_set[k]+=val;
            }else{
                lazy_add[k]+=val;
            }
        }
    }else{
        int mid=(l+r)>>1;
        pushdown(k);
        if(L<=mid){
            update(option,k<<1,l,mid,L,R,val);
        }
        if(R>mid){
            update(option,k<<1|1,mid+1,r,L,R,val);
        }
        pushup(k);
    }
}
ll query(int k,int l,int r,int L,int R){
//  cout<<k<<' '<<l<<' '<<r<<endl;
    if(L<=l&&r<=R){
        return tree[k];
    }else if(!(L>r||R<l)){
        int mid=(l+r)>>1;
        pushdown(k);
        return max(query(k<<1,l,mid,L,R),query(k<<1|1,mid+1,r,L,R));
    }else{
        return -nul;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    build(1,1,n);
    for(int i=1,option,l,r,x;i<=q;i++){
        cin>>option>>l>>r;
        if(option!=3){
            cin>>x;
        //  cout<<endl;
            update(option,1,1,n,l,r,x); 
        }else{
        //  cout<<endl;
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
} 

by MornHus @ 2023-08-24 16:56:45

已经调教成这样了，但还是60pts

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1000006
ll tree[maxn<<2];
ll nul=1e18;
ll lazy_add[maxn<<2];
ll lazy_set[maxn<<2];
int n,q;
void pushup(int k){
    tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
void build(int k,int l,int r){
    lazy_set[k]=nul;
    if(l==r){
        cin>>tree[k];
    }else{
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }
}
void pushdown(int k){
    if(lazy_set[k]!=nul){
        tree[k<<1]=lazy_set[k];
        tree[k<<1|1]=lazy_set[k];
        lazy_add[k<<1]=lazy_add[k<<1|1]=0;
        lazy_set[k]=nul;
    }else if(lazy_add[k]){
        tree[k<<1]+=lazy_add[k];
        tree[k<<1|1]+=lazy_add[k];
        if(lazy_set[k<<1]!=nul){
            lazy_set[k<<1]+=lazy_add[k];
        }else{
            lazy_add[k<<1]+=lazy_add[k];
        }
        if(lazy_set[k<<1|1]!=nul){
            lazy_set[k<<1|1]+=lazy_add[k];
        }else{
            lazy_add[k<<1|1]+=lazy_add[k];
        }
        lazy_add[k]=0;
    }
}
void update(int option,int k,int l,int r,int L,int R,ll val){
    if(L<=l&&r<=R){
        if(option==1){
            tree[k]=val;
            lazy_set[k]=val;
            lazy_add[k]=0;
        }else{
            tree[k]+=val;
            if(lazy_set[k]!=nul){
                lazy_set[k]+=val;
            }else{
                lazy_add[k]+=val;
            }
        }
    }else if(!(L>r||R<l)){
        int mid=(l+r)>>1;
        pushdown(k);
        update(option,k<<1,l,mid,L,R,val);
        update(option,k<<1|1,mid+1,r,L,R,val);
        pushup(k);
    }
}
ll query(int k,int l,int r,int L,int R){
//  cout<<k<<' '<<l<<' '<<r<<endl;
    if(L<=l&&r<=R){
        return tree[k];
    }else if(!(L>r||R<l)){
        int mid=(l+r)>>1;
        pushdown(k);
        return max(query(k<<1,l,mid,L,R),query(k<<1|1,mid+1,r,L,R));
    }else{
        return -nul;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    build(1,1,n);
    for(ll i=1,option,l,r;i<=q;i++){
        ll x;
        cin>>option>>l>>r;
        if(option!=3){
            cin>>x;
        //  cout<<endl;
            update(option,1,1,n,l,r,x); 
        }else{
        //  cout<<endl;
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
}