20pts求调

P1253 扶苏的问题

TMLY114514 @ 2023-12-01 14:51:26

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000010],tree[4000010],lazy1[4000010],lazy2[4000010];
bool lazy2u[4000010];//lazy1为add,lazy2为cover 
int op,n,q,L,R,x;
void update(int num){
    tree[num]=max(tree[num<<1],tree[num<<1|1]);
}
void build(int l,int r,int num){
    lazy2[num]=0;
    tree[num]=-1e9-1;
    if(l==r){
        tree[num]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,num<<1);
    build(mid+1,r,num<<1|1);
    update(num);
    return;
}
void push_down(int num){
    if(lazy2u[num]){
        lazy1[num<<1]=lazy1[num];
        lazy1[num<<1|1]=lazy1[num];
        lazy2[num<<1]=lazy2[num];
        lazy2[num<<1|1]=lazy2[num];
        tree[num<<1]=lazy1[num]+lazy2[num];
        tree[num<<1|1]=lazy1[num]+lazy2[num];
        lazy2u[num<<1]=lazy2u[num<<1|1]=1;
    }else{
        lazy1[num<<1]=lazy1[num];
        lazy1[num<<1|1]=lazy1[num];
        tree[num<<1]+=lazy1[num];
        tree[num<<1|1]+=lazy1[num];
    }
    lazy2u[num]=lazy1[num]=lazy2[num]=0;
}
void modify(int wl,int wr,int l,int r,int num,int x){
    if(wl<=l&&wr>=r){
        lazy1[num]+=x;
        tree[num]+=x;
        return;
    }
    push_down(num);
    int mid=(l+r)>>1;
    if(mid>=wl)modify(wl,wr,l,mid,num<<1,x);
    if(mid<wr)modify(wl,wr,mid+1,r,num<<1|1,x);
    update(num);
    return;
}
void cover(int wl,int wr,int l,int r,int num,int x){
    if(wl<=l&&wr>=r){
        lazy1[num]=0;
        lazy2[num]=x;
        tree[num]=x;
        lazy2u[num]=1;
        return;
    }
    push_down(num);
    int mid=(l+r)>>1;
    if(mid>=wl)cover(wl,wr,l,mid,num<<1,x);
    if(mid<wr)cover(wl,wr,mid+1,r,num<<1|1,x);
    update(num);
    return;
}
int findm(int wl,int wr,int l,int r,int num){
    if(wl<=l&&wr>=r){
        return tree[num];
    }
    push_down(num);
    int mid=(l+r)>>1,ans=-1e9-1;
    if(mid>=wl)ans=max(ans,findm(wl,wr,l,mid,num<<1));
    if(mid<wr)ans=max(ans,findm(wl,wr,mid+1,r,num<<1|1));
    update(num);
    return ans;
}
signed main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    build(1,n,1);
    for(int i=1;i<=q;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%lld",&L,&R,&x);
            cover(L,R,1,n,1,x);
        }else if(op==2){
            scanf("%d%d%lld",&L,&R,&x);
            modify(L,R,1,n,1,x);
        }else{
            scanf("%d%d",&L,&R);
            printf("%lld\n",findm(L,R,1,n,1));
        }
    }
    return 0;
}

|