可过样例1,样例2答案是-9求调

P1253 扶苏的问题

sanye @ 2024-05-26 20:48:13

#include<bits/stdc++.h>
using namespace std;
int n,q,op,a,b,c;
long long shu[1000010],ans[4000010],lazy[4000010],tag[4000010];
inline int ls(int x){
    return x<<1;
}
inline int rs(int x){
    return (x<<1)|1;
}
void pushup(int p){
    //cout<<p<<": "<<ans[ls(p)]<<" "<<ans[rs(p)]<<endl;
    ans[p]=max(ans[ls(p)],ans[rs(p)]);
}
void addtag1(int p){
    if(tag[p]!=10000000000){
        ans[ls(p)]=tag[p];
        ans[rs(p)]=tag[p];
        tag[ls(p)]=tag[p];
        tag[rs(p)]=tag[p];
        lazy[ls(p)]=0;
        lazy[rs(p)]=0;
        tag[p]=10000000000;
    }
}
void addtag2(int p){
    if(lazy[p]){
        addtag1(p);
        ans[ls(p)]+=lazy[p];
        ans[rs(p)]+=lazy[p];
        lazy[ls(p)]+=lazy[p];
        lazy[rs(p)]+=lazy[p];
        lazy[p]=0;
    }
}
void pushback(int p){
    addtag1(p);
    addtag2(p);
}
void build(int p,int l,int r){
    //cout<<"b";
    tag[p]=10000000000;
    if(l==r){
        ans[p]=shu[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
void jia(int p,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
        addtag1(p);
        lazy[p]+=k;
        ans[p]+=k;
        return;
    }
    pushback(p);
    int mid=(l+r)>>1;
    if(x<=mid) jia(ls(p),l,mid,x,y,k);
    if(y>mid) jia(rs(p),mid+1,r,x,y,k);
    pushup(p);
}
void huan(int p,int l,int r,int x,int y,int k){
    if(x<=r&&y>=r){
        ans[p]=k;
        tag[p]=k;
        lazy[p]=0;
        return;
    }
    pushback(p);
    int mid=(l+r)>>1;
    if(x<=mid) huan(ls(p),l,mid,x,y,k);
    if(y>mid) huan(rs(p),mid+1,r,x,y,k);
    pushup(p);
} 
long long cha(int p,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        return ans[p];
    }
    pushback(p);
    int mid=(l+r)>>1;
    long long aans=-99999999999999;
    if(x<=mid) aans=max(cha(ls(p),l,mid,x,y),aans);
    if(y>mid) aans=max(cha(rs(p),mid+1,r,x,y),aans);
    return aans;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%lld",&shu[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++){
    //  for(int j=1;j<=3;j++) cout<<ans[j]<<" "<<tag[j]<<" "<<lazy[j]<<endl;
        //cout<<endl;
        scanf("%lld%lld%lld",&op,&a,&b);
        if(op==1){
            scanf("%lld",&c);
            huan(1,1,n,a,b,c);
        }
        if(op==2){
            scanf("%lld",&c);
            jia(1,1,n,a,b,c);
        }
        if(op==3){
            cout<<cha(1,1,n,a,b)<<endl;
        }
    }
}

|