50分求调

P1253 扶苏的问题

junee @ 2023-11-27 23:42:18

#include<iostream>
#include<algorithm>
using namespace std;
const long long N=1e6+10,inf=-21474836470000;
long long a[N],n,m;
struct node{
    long long l,r,maxn,add,tag;
}tr[N*4];
void pushup(int u){
    tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}
void cover(int u){
    if(tr[u].tag!=inf){
        tr[u<<1].add=tr[u<<1|1].add=0;
        tr[u<<1].tag=tr[u<<1|1].tag=tr[u].tag; 
        tr[u<<1].maxn=tr[u<<1|1].maxn=tr[u].tag;
        tr[u].tag=inf;
    }
}
void adddown(int u){
    if(tr[u].add){
        cover(u);
        tr[u<<1].maxn+=tr[u].add,tr[u<<1|1].maxn+=tr[u].add;
        tr[u<<1].add+=tr[u].add,tr[u<<1|1].add+=tr[u].add;
        tr[u].add=0;
    }
}
void pushdown(int u){
    cover(u);
    adddown(u);
}
void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        tr[u].maxn=a[l];
        tr[u].tag=inf;
        tr[u].add=0;
        return;
    }
    long long mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void addd(int u,int l,int r,int d){
    if(tr[u].l>=l&&tr[u].r<=r){
        pushdown(u);
        tr[u].maxn+=d;
        tr[u].add+=d;
        return;
    }
    pushdown(u);
    long long mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid)addd(u<<1,l,r,d);
    if(r>mid)addd(u<<1|1,l,r,d);
    pushup(u);
}
void modify(int u,int l,int r,int x){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].add=0;
        tr[u].maxn=tr[u].tag=x;
        return;
    }
    pushdown(u);
    long long mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid)modify(u<<1,l,r,x);
    if(r>mid)modify(u<<1|1,l,r,x);
    pushup(u);
}
long long query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)
        return tr[u].maxn;
    pushdown(u);
    long long v=-1e9-1,mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid)v=max(v,query(u<<1,l,r));
    if(r>mid)v=max(v,query(u<<1|1,l,r));
    return v;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=n*4;i++)tr[i].tag=inf;
    for(int i=1;i<=m;i++){
        long long op,l,r,x;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1){
            scanf("%lld",&x);
            modify(1,l,r,x);
        }
        if(op==2){
            scanf("%lld",&x);
            addd(1,l,r,x);
        }
        if(op==3){
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
}

by junee @ 2023-11-27 23:52:29

警钟撅烂! query函数中的v值要开小一点-1e9不够,可以开到-21474836470000 此贴结


|