求调60pts

yueyan_WZF @ 2024-08-22 12:50:32

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;
    long long sum,maxx,lazy1,lazy2;
}z[9000003];
long long a[1000020];
int n,q;
void updata(int k){
    z[k].sum=z[k*2].sum+z[k*2+1].sum;
    z[k].maxx=max(z[k*2].maxx,z[k*2+1].maxx);
}
void pushdown(int k){   
    if(z[k].lazy1!=-1e17){
        z[k*2].sum=1ll*(z[k*2].r-z[k*2].l+1)*z[k].lazy1;
        z[k*2+1].sum=1ll*(z[k*2+1].r-z[k*2+1].l+1)*z[k].lazy1;
        z[k*2].maxx=z[k*2+1].maxx=z[k].lazy1;
        z[k*2].lazy2=z[k*2+1].lazy2=0;
        z[k*2].lazy1=z[k].lazy1;
        z[k*2+1].lazy1=z[k].lazy1;
        z[k].lazy1=-1e17;
    }
    if(z[k].lazy2){
        z[k*2].sum+=1ll*(z[k*2].r-z[k*2].l+1)*z[k].lazy2;
        z[k*2+1].sum+=1ll*(z[k*2+1].r-z[k*2+1].l+1)*z[k].lazy2;
        z[k*2].maxx+=z[k].lazy2;
        z[k*2+1].maxx+=z[k].lazy2;
        z[k*2].lazy2+=z[k].lazy2;
        z[k*2+1].lazy2+=z[k].lazy2;
        z[k].lazy2=0;
    }

}
void build(int l,int r,int k){
    z[k].l=l;
    z[k].r=r;
    z[k].lazy2=0;
    z[k].lazy1=-1e17;
    z[k].maxx=-1e17;
    if(l==r){
        z[k].sum=a[l];
        z[k].maxx=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
    updata(k);
}
void chan1(int l,int r,int k,int a){
    if(z[k].l>=l&&z[k].r<=r){
        z[k].sum=1ll*(z[k].r-z[k].l+1)*a;
        z[k].maxx=a;
        z[k].lazy1=a;
        return ;
    }
    pushdown(k);
    int mid=(z[k].l+z[k].r)>>1;
    if(l<=mid){
        chan1(l,r,k*2,a);
    }
    if(r>mid){
        chan1(l,r,k*2+1,a);
    }
    updata(k);
}
void chan2(int l,int r,int k,int a){
    if(z[k].l>=l&&z[k].r<=r){
        z[k].sum+=1ll*(z[k].r-z[k].l+1)*a;
        z[k].maxx+=a;
        z[k].lazy2+=a;
        return ;
    }
    pushdown(k);
    int mid=(z[k].l+z[k].r)>>1;
    if(l<=mid){
        chan2(l,r,k*2,a);
    }
    if(r>mid){
        chan2(l,r,k*2+1,a);
    }
    updata(k);
}
long long find(int l,int r,int k){
    if(z[k].l>=l&&z[k].r<=r){
        return z[k].maxx;
    }
    pushdown(k);
    int mid=(z[k].r+z[k].l)>>1;
    long long maxx=-1e17;
    if(l<=mid){
        maxx=find(l,r,k*2);
    }
    if(r>mid){
        maxx=max(maxx,find(l,r,k*2+1));
    }
    return maxx;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int l,r;
            int x;
            scanf("%d%d%d",&l,&r,&x);
            chan1(l,r,1,x);
        }
        if(opt==2){
            int l,r;
            int x;
            scanf("%d%d%d",&l,&r,&x);
            chan2(l,r,1,x);
        }
        if(opt==3){
            int l,r,x;
            scanf("%d%d",&l,&r);
            printf("%lld\n",find(l,r,1));
        }
    }
}

by lyas145 @ 2024-08-22 13:28:34

@yueyan_WZF 你在 chan1 函数中修改时没把 lazy2 清空

by Eason20120229 @ 2024-08-22 13:31:16

@yueyan_WZF pushdown要放在每个函数的最前面，不然会导致两种标签同时存在。\ AC代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;
    long long sum,maxx,lazy1,lazy2;
}z[9000003];
long long a[1000020];
int n,q;
void updata(int k){
    z[k].sum=z[k*2].sum+z[k*2+1].sum;
    z[k].maxx=max(z[k*2].maxx,z[k*2+1].maxx);
}
void pushdown(int k){   
    if(z[k].lazy1!=-1e17){
        z[k*2].sum=1ll*(z[k*2].r-z[k*2].l+1)*z[k].lazy1;
        z[k*2+1].sum=1ll*(z[k*2+1].r-z[k*2+1].l+1)*z[k].lazy1;
        z[k*2].maxx=z[k*2+1].maxx=z[k].lazy1;
        z[k*2].lazy2=z[k*2+1].lazy2=0;
        z[k*2].lazy1=z[k].lazy1;
        z[k*2+1].lazy1=z[k].lazy1;
        z[k].lazy1=-1e17;
    }
    if(z[k].lazy2){
        z[k*2].sum+=1ll*(z[k*2].r-z[k*2].l+1)*z[k].lazy2;
        z[k*2+1].sum+=1ll*(z[k*2+1].r-z[k*2+1].l+1)*z[k].lazy2;
        z[k*2].maxx+=z[k].lazy2;
        z[k*2+1].maxx+=z[k].lazy2;
        z[k*2].lazy2+=z[k].lazy2;
        z[k*2+1].lazy2+=z[k].lazy2;
        z[k].lazy2=0;
    }

}
void build(int l,int r,int k){
    z[k].l=l;
    z[k].r=r;
    z[k].lazy2=0;
    z[k].lazy1=-1e17;
    z[k].maxx=-1e17;
    if(l==r){
        z[k].sum=a[l];
        z[k].maxx=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
    updata(k);
}
void chan1(int l,int r,int k,int a){
    pushdown(k);
    if(z[k].l>=l&&z[k].r<=r){
        z[k].sum=1ll*(z[k].r-z[k].l+1)*a;
        z[k].maxx=a;
        z[k].lazy1=a;
        return ;
    }
    int mid=(z[k].l+z[k].r)>>1;
    if(l<=mid){
        chan1(l,r,k*2,a);
    }
    if(r>mid){
        chan1(l,r,k*2+1,a);
    }
    updata(k);
}
void chan2(int l,int r,int k,int a){
    pushdown(k);
    if(z[k].l>=l&&z[k].r<=r){
        z[k].sum+=1ll*(z[k].r-z[k].l+1)*a;
        z[k].maxx+=a;
        z[k].lazy2+=a;
        return ;
    }
    int mid=(z[k].l+z[k].r)>>1;
    if(l<=mid){
        chan2(l,r,k*2,a);
    }
    if(r>mid){
        chan2(l,r,k*2+1,a);
    }
    updata(k);
}
long long find(int l,int r,int k){
    pushdown(k);
    if(z[k].l>=l&&z[k].r<=r){
        return z[k].maxx;
    }
    int mid=(z[k].r+z[k].l)>>1;
    long long maxx=-1e17;
    if(l<=mid){
        maxx=find(l,r,k*2);
    }
    if(r>mid){
        maxx=max(maxx,find(l,r,k*2+1));
    }
    return maxx;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int l,r;
            int x;
            scanf("%d%d%d",&l,&r,&x);
            chan1(l,r,1,x);
        }
        if(opt==2){
            int l,r;
            int x;
            scanf("%d%d%d",&l,&r,&x);
            chan2(l,r,1,x);
        }
        if(opt==3){
            int l,r,x;
            scanf("%d%d",&l,&r);
            printf("%lld\n",find(l,r,1));
        }
    }
}

求关注！

by Eason20120229 @ 2024-08-22 13:31:44

@yueyan_WZF 求关注

by yueyan_WZF @ 2024-08-22 13:46:24

@Eason20120229 关了，感谢

by yueyan_WZF @ 2024-08-22 13:46:54

@lyas145 感谢，orz