悬3个关求调

Z_kazuha @ 2024-08-14 21:15:03

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000005;
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
ll n,q;
ll a[N],tree[N<<2],tagp[N<<2],tagm[N<<2];
void pushup(ll p){
    tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void build(ll p,ll pl,ll pr){
    if(pl==pr){
        tree[p]=a[pl];
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    pushup(p);
}
void addtag(ll p,ll x,ll o){
    if(o==1){
        tagp[p]=0;
        tree[p]=x;
        tagm[p]=x; 
    }else{
        if(tagm[p]){
            tagm[p]+=x;
            tree[p]+=x;
        }else{
            tagp[p]+=x;
            tree[p]+=x;
        }
    }
}
void pushdown(ll p){
    if(tagm[p]){
        addtag(ls(p),tagm[p],1);
        addtag(rs(p),tagm[p],1);
        tagm[p]=0;
        tagp[p]=0;
    }else{
        addtag(ls(p),tagp[p],0);
        addtag(rs(p),tagp[p],0);
        tagp[p]=0;
    }
}
void update(ll p,ll L,ll R,ll pl,ll pr,ll x,ll o){
    if(L<=pl&&R>=pr){
        addtag(p,x,o);
        return;
    }
    pushdown(p);
    ll mid=(pl+pr)>>1;
    if(L<=mid)update(ls(p),L,R,pl,mid,x,o);
    if(R>mid)update(rs(p),L,R,mid+1,pr,x,o);
    pushup(p);
}
ll query(ll p,ll L,ll R,ll pl,ll pr){
    if(L<=pl&&R>=pr){
        return tree[p];
    }
    pushdown(p);
    ll res=-0x3ffff;
    ll mid=(pl+pr)>>1;
    if(L<=mid)res=max(res,query(p,L,R,pl,mid));
    if(R>mid)res=max(res,query(p,L,R,mid+1,pr));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        ll o,l,r,x;
        cin>>o>>l>>r;
        if(o==3){
            cout<<query(1,l,r,1,n)<<endl;
        }else{
            cin>>x;
            update(1,l,r,1,n,x,o);
        //  for(int i=1;i<=(n<<2);i++)cout<<tree[i]<<" ";
        }
    }
    return 0;
}

by Nihachu @ 2024-08-15 15:37:25

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define ll long long
const int N=1000005;
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
ll n,q;
ll a[N],tree[N<<2],tagp[N<<2];
pair<int,int> tagm[N<<2];
void pushup(ll p){
    tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void build(ll p,ll pl,ll pr){
    if(pl==pr){
        tree[p]=a[pl];
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    pushup(p);
}
void addtag(ll p,ll x,ll o){
    if(o==1){
        tagp[p]=0;
        tree[p]=x;
        tagm[p]={1,x}; 
    }
    else{
        if(tagm[p].fi){
            tagm[p].se+=x;
            tree[p]+=x;
        }else{
            tagp[p]+=x;
            tree[p]+=x;
        }
    }
}
void pushdown(ll p){
    if(tagm[p].fi){
        addtag(ls(p),tagm[p].se,1);    
        addtag(rs(p),tagm[p].se,1);
        tagm[p].fi=0;
        tagm[p].se=0;
        tagp[p]=0;
    }else{
        addtag(ls(p),tagp[p],0);
        addtag(rs(p),tagp[p],0);
        tagp[p]=0;
    }
}

void update(ll p,ll L,ll R,ll pl,ll pr,ll x,ll o){
    if(L<=pl&&R>=pr){
        addtag(p,x,o);
        return;
    }
    pushdown(p);
    ll mid=(pl+pr)>>1;
    if(L<=mid)update(ls(p),L,R,pl,mid,x,o);
    if(R>mid)update(rs(p),L,R,mid+1,pr,x,o);
    pushup(p);
}
ll query(ll p,ll L,ll R,ll pl,ll pr){
    if(L<=pl&&R>=pr){
        return tree[p];
    }
    pushdown(p);
    ll res=-1e18;
    ll mid=(pl+pr)>>1;
    if(L<=mid)res=max(res,query(ls(p),L,R,pl,mid));
    if(R>mid)res=max(res,query(rs(p),L,R,mid+1,pr));
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        ll o,l,r,x;
        cin>>o>>l>>r;
        if(o==3){
            cout<<query(1,l,r,1,n)<<endl;
        }else{
            cin>>x;
            update(1,l,r,1,n,x,o);
        } 
    }
    return 0;
}

/*
6 1
1 1 4 5 1 4
1 1 2 6
*/