自做的赋值,未看tj,求dalao们看法(求调)

P1253 扶苏的问题

lizishuoo @ 2022-08-17 10:42:48

#include<iostream>
#include<cstdio>
#define ls i<<1
#define rs i<<1|1
#define ll long long
#define mid (l+r)>>1
using namespace std;
const int N=1e6+99;
ll n,q;int a[N];
struct node{
    ll i,l,r;
    ll ma,sum;//ma最大值   sum和 
    ll ld=0,qj=0;//ld 区间懒标记   qj统一赋值懒标记 
}tr[4*N];
void pushup(ll i){ tr[i].ma=max(tr[ls].ma,tr[rs].ma);tr[i].sum=tr[ls].sum+tr[rs].sum; }
void build(ll i,ll l,ll r,int a[]){
    tr[i].l=l,tr[i].r=r;
    if(l==r){
        tr[i].sum=tr[i].ma=a[l];
        return;
    }
    ll miid=(tr[i].l+tr[i].r)/2;
    build(ls,l,miid,a);
    build(rs,miid+1,r,a);
    pushup(i);
}
void pushdown(ll i){
    tr[ls].ld+=tr[i].ld;
    tr[rs].ld+=tr[i].ld;
    tr[ls].qj=tr[rs].qj=tr[i].qj;
    if(tr[ls].qj==0){
        tr[ls].ma+=tr[i].ld;
        tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[i].ld;
    }else{
        tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[i].qj;
        tr[ls].ma=tr[i].qj;
        tr[ls].ld=0;
    }

    if(tr[rs].qj==0){
        tr[rs].ma+=tr[i].ld;
        tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[i].ld;
    }else{
        tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[i].qj;
        tr[rs].ma=tr[i].qj;
        tr[rs].ld=0;
    }
    tr[i].ld=tr[i].qj=0;
}
ll maxx(ll i,ll l,ll r){//找最大值 
    if(l<=tr[i].l&&tr[i].r<=r){
        return tr[i].ma;
    }
    pushdown(i);
    ll ret=0;
    if(l<=tr[ls].r) ret=max(ret,maxx(ls,l,r));
    if(tr[rs].l<=r) ret=max(ret,maxx(rs,l,r));
    return ret;
}
void add_qj(ll i,ll l,ll r,ll k){//区间修改 
    if(tr[i].l>=l&&tr[i].r<=r){
        tr[i].ld+=k;
        tr[i].ma+=k;
        tr[i].sum+=(tr[i].r-tr[i].l+1)*k;
        return ;
    }
    pushdown(i);
    if(tr[ls].r>=l) add_qj(ls,l,r,k);
    if(tr[rs].l<=r) add_qj(rs,l,r,k);
    pushup(i);
}
void all(ll i,ll l,ll r,ll k){//赋值 
    if(l<=tr[i].l&&tr[i].r<=r){
        tr[i].sum+=(tr[i].r-tr[i].l+1)*k;
        tr[i].qj=tr[i].ma=k;
        return ;
    }
    pushdown(i);
    if(tr[ls].r>=l) all(ls,l,r,k);
    if(tr[rs].l<=r) all(rs,l,r,k);
    //tr[i].ma=max(tr[i].ma,max(tr[ls].ma,tr[rs].ma));
    pushup(i);
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n,a);
    while(q--){
        ll op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            all(1,x,y,k);
        }else if(op==2){
            cin>>x>>y>>k;
            add_qj(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<maxx(1,x,y)<<endl;
        }
    }
    return 0;
}

水40f 样例2过不了


|