50分,求助

P1253 扶苏的问题

leozty @ 2022-08-06 16:10:54

#include <bits/stdc++.h>
using namespace std;
long long maxv[50000010],a[10000010];
long long lazy[50000010];
long long lazy1[50000010];
long long n,q;
void pushdown1(long long id){
    if(lazy[id]!=-1145141919810){
        lazy[id*2]=lazy[id];
        lazy[id*2+1]=lazy[id];
        maxv[id*2]=lazy[id];
        maxv[id*2+1]=lazy[id];
        lazy[id]=-1145141919810;
    }
    if(lazy1[id]){
        lazy1[id*2]+=lazy1[id];
        lazy1[id*2+1]+=lazy1[id];
        maxv[id*2]+=lazy1[id];
        maxv[id*2+1]+=lazy1[id];
        lazy1[id]=0;
    }
}
void pushdown(long long id){
    lazy1[id]=0;
    lazy1[id*2]=0;
    lazy1[id*2+1]=0;
    pushdown1(id);
}
void update(long long id,long long l,long long r,long long x,long long y,long long v){
    if(x<=l&&y>=r){
        maxv[id]=v;
        lazy[id]=v;
        return;
    }
    pushdown(id);
    long long mid=(l+r)/2;
    if(x<=mid){
        update(id*2,l,mid,x,y,v);
    }
    if(y>mid){
        update(id*2+1,mid+1,r,x,y,v);
    }
    maxv[id]=max(maxv[id*2],maxv[id*2+1]);
}
void update1(long long id,long long l,long long r,long long x,long long y,long long v){
    if(x<=l&&y>=r){
        maxv[id]+=v;
        lazy1[id]+=v;
        return;
    }
    pushdown1(id);
    long long mid=(l+r)/2;
    if(x<=mid){
        update1(id*2,l,mid,x,y,v);
    }
    if(y>mid){
        update1(id*2+1,mid+1,r,x,y,v);
    }
    maxv[id]=max(maxv[id*2],maxv[id*2+1]);
}
long long question(long long id,long long l,long long r,long long x,long long y){
    if(x<=l&&y>=r){
        return maxv[id];
    }
    pushdown1(id);
    long long mid=(l+r)/2;
    long long temp1=0,temp2=0;
    if(x<=mid){
        temp1=question(id*2,l,mid,x,y);
    }
    if(y>mid){
        temp2=question(id*2+1,mid+1,r,x,y);
    }
    return max(temp1,temp2);
}
int main(){
    cin>>n;
    cin>>q;
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        update(1,1,n,i,i,a[i]);
    }
    for(long long i=1;i<=40000005;i++){
        lazy[i]=-1145141919810;
    }
    for(long long i=1;i<=q;i++){
        int op;
        cin>>op;
        long long l,r;
        long long x;
        if(op==1){
            scanf("%lld %lld %lld",&l,&r,&x);
            update(1,1,n,l,r,x);
        }
        if(op==2){
            scanf("%lld %lld %lld",&l,&r,&x);
            update1(1,1,n,l,r,x);
        }
        if(op==3){
            scanf("%lld %lld",&l,&r);
            long long ans=question(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by zhsm_ @ 2022-08-06 16:19:40

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
struct node{
    ll l,r,Max,laz_add,laz_cover_need,laz_cover_num;
} tre[4000010];
ll n,m,z,x,y,c,ans,a[1000010];
void make(ll l,ll r,ll s){//建树
    tre[s].l=l;
    tre[s].r=r;
    if(l==r){
        tre[s].Max=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    make(l,mid,s<<1);
    make(mid+1,r,s<<1|1);
    tre[s].Max=max(tre[s<<1].Max,tre[s<<1|1].Max);
    return;
}
void push_d(ll s)//清除懒惰标记
{
    if(tre[s].laz_cover_need==1){
        tre[s*2].laz_cover_need=1;
        tre[s*2].laz_cover_num=tre[s].laz_cover_num;
        tre[s*2].laz_add=0;
        tre[s*2].Max=tre[s].laz_cover_num;
        tre[s*2+1].laz_cover_need=1;
        tre[s*2+1].laz_cover_num=tre[s].laz_cover_num;
        tre[s*2+1].laz_add=0;
        tre[s*2+1].Max=tre[s].laz_cover_num;
        tre[s].laz_cover_need=0;
        tre[s].laz_cover_num=0; 
    }
    if(tre[s].laz_add!=0){
        tre[s*2].Max+=tre[s].laz_add;
        tre[s*2].laz_add+=tre[s].laz_add;
        tre[s*2+1].Max+=tre[s].laz_add;
        tre[s*2+1].laz_add+=tre[s].laz_add;
        tre[s].laz_add=0;
    }
    return;
}
void change_add(ll l,ll r,ll s,ll cc){//区间加减
    if(tre[s].l>=l&&tre[s].r<=r){
        tre[s].Max+=cc;
        tre[s].laz_add+=cc;
        return;
    }
    push_d(s);
    if(tre[s*2].r>=l)
        change_add(l,r,s*2,cc);
    if(tre[s*2+1].l<=r)
        change_add(l,r,s*2+1,cc);
    tre[s].Max=max(tre[s*2].Max,tre[s*2+1].Max);
    return;
}
void change_cover(ll l,ll r,ll s,ll cc){//区间修改
    if(tre[s].l>=l&&tre[s].r<=r){
        tre[s].laz_add=0;
        tre[s].Max=cc;
        tre[s].laz_cover_need=1;
        tre[s].laz_cover_num=cc;
        return;
    }
    push_d(s);
    if(tre[s*2].r>=l)
        change_cover(l,r,s*2,cc);
    if(tre[s*2+1].l<=r)
        change_cover(l,r,s*2+1,cc);
    tre[s].Max=max(tre[s*2].Max,tre[s*2+1].Max);
    return;
}
ll ask(ll l,ll r,ll s){//询问区间最大值
    if(tre[s].l>=l&&tre[s].r<=r)
        return tre[s].Max;
    push_d(s);
    ll value=(ll)-1e15;
    if(tre[s*2].r>=l)
        value=max(value,ask(l,r,s*2));
    if(tre[s*2+1].l<=r)
        value=max(value,ask(l,r,s*2+1));
    return value;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i];
    make(1,n,1);
    for(ll i=1;i<=m;i++){
        ll q,l,r,num;
        cin>>q;
        if(q==1){
            cin>>l>>r>>num;
            change_cover(l,r,1,num);
        }
        else if(q==2){
            cin>>l>>r>>num;
            change_add(l,r,1,num);
        }
        else{
            cin>>l>>r;
            cout<<ask(l,r,1)<<"\n";
        }
    }
    return 0;
}

by ls2128606 @ 2022-08-06 16:58:22

超了一半 有十名特判也能过 https://www.luogu.com.cn/paste/lkj4rmbl


by leozty @ 2022-08-06 18:37:25

什么意思


by leozty @ 2022-08-07 07:49:24

已经对了,谢谢各位大佬的帮助


|