40pts求调（玄关）

Tiskan_H @ 2024-07-13 20:57:25

#include<bits/stdc++.h>
#define int long long
#define N 1000010
using namespace std;

int n,m;
int a[N];

struct node{
    int l,r;
    int dat,laz,lat;
}tr[4*N];

void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    tr[p].dat=max(tr[2*p].dat,tr[2*p+1].dat);
    tr[p].lat=-1e18;
}
void spread(int p){
    if(tr[p].lat>-1e18){
        tr[2*p].dat=tr[p].lat,tr[2*p+1].dat=tr[p].lat;
        tr[2*p].lat=tr[p].lat;
        tr[2*p+1].lat=tr[p].lat;
        tr[p].lat=0;
    }
    if(tr[p].laz){
        tr[2*p].dat=max(tr[2*p].dat+tr[p].laz,tr[2*p].dat);
        tr[2*p+1].dat=max(tr[2*p+1].dat+tr[p].laz,tr[2*p+1].dat);
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void change(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].laz+=k,
        tr[p].dat=max(tr[p].dat+k,tr[p].dat);
        return;
    }
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid) change(2*p,l,r,k);
    if(r>mid) change(2*p+1,l,r,k);
    tr[p].dat=max(tr[2*p].dat,tr[2*p+1].dat);
}
void turn(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].laz=k,
        tr[p].dat=k;
        return;
    }
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    int val=-1e18;
    if(l<=mid) turn(2*p,l,r,k);
    if(r>mid) turn(2*p+1,l,r,k);
    tr[p].dat=k;
}
int ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    int val=-1e20;
    if(l<=mid) val=max(ask(2*p,l,r),val);
    if(r>mid) val=max(ask(2*p+1,l,r),val);
    return val;
}

signed main(){
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
        std::cin>>a[i];
    build(1,1,n);
    //for(int i=1;i<=2*n+1;i++)
    //  cout<<tr[i].l<<","<<tr[i].r<<":"<<tr[i].dat<<endl;
    for(int i=1;i<=m;i++){
        int xs;
        std::cin>>xs;
        if(xs==2){
            int x,y,k;
            std::cin>>x>>y>>k;
            change(1,x,y,k);
        }else if(xs==1){
            int x,y,k;
            std::cin>>x>>y>>k;
            //turn(1,x,y,k);
        }else{
            int l,r;
            std::cin>>l>>r;
            std::cout<<ask(1,l,r)<<"\n";
        }
        //for(int i=1;i<=2*n+1;i++)
        //  cout<<tr[i].l<<","<<tr[i].r<<":"<<tr[i].dat<<endl;
    }
    return 0;
}

/*
8 8
23 45 645 -32 34 9 -12 5
2 1 8 1
*/

by Mr_Dolphin @ 2024-07-15 11:49:27

@hhn01

#include<bits/stdc++.h>
#define int long long
#define N 1000010
using namespace std;

int n,m;
int a[N];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct node{
    int l,r;
    int dat,laz,lat,f;
}tr[4*N];

void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    tr[p].dat=max(tr[2*p].dat,tr[2*p+1].dat);
}
void spread(int p){
    if(tr[p].f){
        tr[p<<1].f=tr[p<<1|1].f=1;
        tr[2*p].dat=tr[p].lat,tr[2*p+1].dat=tr[p].lat;
        tr[2*p].lat=tr[p].lat;
        tr[2*p+1].lat=tr[p].lat;
        tr[p<<1].laz=tr[p<<1|1].laz=0;
        tr[p].f=tr[p].lat=0;
    }
    if(tr[p].laz){
        tr[2*p].dat+=tr[p].laz;
        tr[2*p+1].dat+=tr[p].laz;
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void change(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].laz+=k,
        tr[p].dat+=k;
        return;
    }
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid) change(2*p,l,r,k);
    if(r>mid) change(2*p+1,l,r,k);
    tr[p].dat=max(tr[2*p].dat,tr[2*p+1].dat);
}
void turn(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].lat=k;
        tr[p].f=1;
        tr[p].laz=0,
        tr[p].dat=k;
        return;
    }
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid) turn(2*p,l,r,k);
    if(r>mid) turn(2*p+1,l,r,k);
    tr[p].dat=max(tr[p<<1].dat,tr[p<<1|1].dat);
}
int ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    int val=LONG_LONG_MIN;
    if(l<=mid) val=max(ask(2*p,l,r),val);
    if(r>mid) val=max(ask(2*p+1,l,r),val);
    return val;
}

signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int xs;
        xs=read();
        if(xs==2){
            int x,y,k;
            x=read(),y=read(),k=read();
            change(1,x,y,k);
        }else if(xs==1){
            int x,y,k;
            x=read(),y=read(),k=read();
            turn(1,x,y,k);
        }else{
            int l,r;
            l=read(),r=read();
            printf("%lld\n",ask(1,l,r));
        }
    }
    return 0;
}

by Tiskan_H @ 2024-07-15 13:18:13

@Mr_Dolphin 非常感谢，已关！