萌新姝子刚学线段树,60pts求助,WA#7~10

P1253 扶苏的问题

somebody_kang @ 2022-08-27 11:48:59

显然不是妹子

个人认为我马蜂海星,比较朴素,学过英语的应该都看得懂,也没有用结构体,指针等花里胡哨的东西 CODE:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll c[5000001],lazy[5000001],a[1000001],lazy1[5000001];
const ll inf=-1e15;
inline ll ls(ll p){return p<<1;}
inline ll rs(ll p){return (p<<1)|1;}
void build(int l,int r,int p){
    lazy1[p]=inf;
    if(l==r){
        c[p]=a[l];return;
    }
    int mid=l+(r-l)/2;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    c[p]=max(c[ls(p)],c[rs(p)]);
}
void cover_down(int l,int r,int p){
    int mid=l+(r-l)/2;
    if(lazy1[p]!=inf){
        c[ls(p)]=lazy1[p];
        c[rs(p)]=lazy1[p];
        lazy[ls(p)]=0;lazy[rs(p)]=0;
        lazy1[ls(p)]=lazy1[p];lazy1[rs(p)]=lazy1[p];
        lazy1[p]=0;
    }
}
void add_down(int l,int r,int p){
    cover_down(l,r,p);
    if(lazy[p]){
        c[ls(p)]+=lazy[p];
        c[rs(p)]+=lazy[p];
        lazy[ls(p)]+=lazy[p];
        lazy[rs(p)]+=lazy[p];
        lazy[p]=0;
    }
}
ll getmax(int l,int r,int x,int y,int p){
    if(l>y||r<x) return inf;
    if(l>=x&&r<=y) return c[p];
    cover_down(l,r,p);
    add_down(l,r,p);
    int mid=l+(r-l)/2;
    ll maxn=inf;
    if(x<=mid) maxn=max(maxn,getmax(l,mid,x,y,ls(p)));
    if(mid<r) maxn=max(maxn,getmax(mid+1,r,x,y,rs(p)));
    return maxn; 
}
void update_cover(int l,int r,int x,int y,int p,ll k){
    if(l>y||r<x) return;
    if(l>=x&&r<=y){
        lazy1[p]=k;
        c[p]=k;
        return;
    }
    ll mid=l+(r-l)/2;
    cover_down(l,r,p);
    add_down(l,r,p);
    if(x<=mid) update_cover(l,mid,x,y,ls(p),k);
    if(y>mid) update_cover(mid+1,r,x,y,rs(p),k);
    c[p]=max(c[ls(p)],c[rs(p)]);
}
void update_add(int l,int r,int x,int y,int p,ll k){
    if(l>y||r<x) return;
    if(l>=x&&r<=y){
        lazy[p]+=k;
        c[p]+=k;
        return;
    }
    ll mid=l+(r-l)/2;
    cover_down(l,r,p);
    add_down(l,r,p);
    if(x<=mid) update_add(l,mid,x,y,ls(p),k);
    if(y>mid) update_add(mid+1,r,x,y,rs(p),k);
    c[p]=max(c[ls(p)],c[rs(p)]);
}
int main(){
    std::ios::sync_with_stdio(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=q;++i){
        int x,y,z;
        ll k;
        cin>>z;
        if(z==1){
            cin>>x>>y>>k;
            update_cover(1,n,x,y,1,k);
        }
        else if(z==2){
            cin>>x>>y>>k;
            update_add(1,n,x,y,1,k);
        }
        else if(z==3){
            cin>>x>>y;
            cout<<getmax(1,n,x,y,1)<<endl;
        }
    }
}

by bamboo12345 @ 2022-08-27 12:16:14

@somebody_kang 调出来了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll c[5000001],lazy[5000001],a[1000001],lazy1[5000001];
const ll inf=-1e15;
inline ll ls(ll p){return p<<1;}
inline ll rs(ll p){return (p<<1)|1;}
void build(int l,int r,int p){
    lazy1[p]=inf;
    if(l==r){
        c[p]=a[l];return;
    }
    int mid=l+(r-l)/2;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    c[p]=max(c[ls(p)],c[rs(p)]);
}
void cover_down(int l,int r,int p){
    int mid=l+(r-l)/2;
    if(lazy1[p]!=inf){
        c[ls(p)]=lazy1[p];
        c[rs(p)]=lazy1[p];
        lazy[ls(p)]=0;lazy[rs(p)]=0;
        lazy1[ls(p)]=lazy1[p];lazy1[rs(p)]=lazy1[p];
        lazy1[p]=inf;///
    }
}
void add_down(int l,int r,int p){
    if(lazy[p]){
        cover_down(l,r,p);///
        c[ls(p)]+=lazy[p];
        c[rs(p)]+=lazy[p];
        lazy[ls(p)]+=lazy[p];
        lazy[rs(p)]+=lazy[p];
        lazy[p]=0;
    }
}
ll getmax(int l,int r,int x,int y,int p){
    if(l>y||r<x) return inf;
    if(l>=x&&r<=y) return c[p];
    cover_down(l,r,p);
    add_down(l,r,p);
    int mid=l+(r-l)/2;
    ll maxn=inf;
    if(x<=mid) maxn=max(maxn,getmax(l,mid,x,y,ls(p)));
    if(mid<y) maxn=max(maxn,getmax(mid+1,r,x,y,rs(p)));///
    return maxn; 
}
void update_cover(int l,int r,int x,int y,int p,ll k){
    if(l>y||r<x) return;
    if(l>=x&&r<=y){
        lazy1[p]=k;
        c[p]=k;
        lazy[p]=0;///
        return;
    }
    ll mid=l+(r-l)/2;
    cover_down(l,r,p);
    add_down(l,r,p);
    if(x<=mid) update_cover(l,mid,x,y,ls(p),k);
    if(y>mid) update_cover(mid+1,r,x,y,rs(p),k);
    c[p]=max(c[ls(p)],c[rs(p)]);
}
void update_add(int l,int r,int x,int y,int p,ll k){
    if(l>y||r<x) return;
    if(l>=x&&r<=y){
        cover_down(l,r,p);
        lazy[p]+=k;
        c[p]+=k;
        return;
    }
    ll mid=l+(r-l)/2;
    cover_down(l,r,p);
    add_down(l,r,p);
    if(x<=mid) update_add(l,mid,x,y,ls(p),k);
    if(y>mid) update_add(mid+1,r,x,y,rs(p),k);
    c[p]=max(c[ls(p)],c[rs(p)]);
}
int main(){
    std::ios::sync_with_stdio(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=q;++i){
        int x,y,z;
        ll k;
        cin>>z;
        if(z==1){
            cin>>x>>y>>k;
            update_cover(1,n,x,y,1,k);
        }
        else if(z==2){
            cin>>x>>y>>k;
            update_add(1,n,x,y,1,k);
        }
        else if(z==3){
            cin>>x>>y;
            cout<<getmax(1,n,x,y,1)<<endl;
        }
    }
}

/// 的是改动的地方


by somebody_kang @ 2022-08-27 18:37:32

@bamboo123 WOC,谢大佬orz


by somebody_kang @ 2022-08-27 18:43:06

@bamboo123 好多地方都是变量打错了,也有一些地方没有考虑清楚。感谢您花时间帮我查错,orzorz


by bamboo12345 @ 2022-08-27 18:50:40

@somebody_kang 没事,举手之劳而已


|