MAXN=1e6+5会RE。改2e6就AC

P1253 扶苏的问题

steveyang137 @ 2024-07-20 10:57:53

如题,n应该最大只有1e6啊,为什么需要开到更大呢

#include<iostream>
#include<cstdio>
using namespace std;

#define int long long
const int MAXN=2e6+5,NON=1e18+1;
int n,q;
struct node {
    int mx,cover_tag,sum_tag;
} seg[MAXN<<2];
int a[MAXN];

node merge(node s1,node s2) {
    node s3;
    s3.mx=max(s1.mx,s2.mx);
    s3.cover_tag=NON;
    s3.sum_tag=0;
    return s3;
}

void build(int p,int l,int r) {
    if(l==r) {
        seg[p].mx=a[l];
        seg[p].cover_tag=NON;
        seg[p].sum_tag=0;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    seg[p]=merge(seg[p<<1],seg[p<<1|1]);
    return;
}

void pushdown(int p) {
    if(seg[p].cover_tag!=NON) {
        seg[p<<1].cover_tag=seg[p<<1|1].cover_tag=seg[p].cover_tag;
        seg[p<<1].mx=seg[p<<1|1].mx=seg[p].mx;
        seg[p<<1].sum_tag=seg[p<<1|1].sum_tag=0;
        seg[p].cover_tag=NON;
        seg[p].sum_tag=0;
    }
    if(seg[p].sum_tag) {
        seg[p<<1].mx+=seg[p].sum_tag;
        seg[p<<1|1].mx+=seg[p].sum_tag;
        seg[p<<1].sum_tag+=seg[p].sum_tag;
        seg[p<<1|1].sum_tag+=seg[p].sum_tag;
        seg[p].sum_tag=0;
    }
    // cout<<p<<":"<<seg[p].mx<<endl;
    return;
}

void modify1(int p,int l,int r,int s,int t,int k) {
    if(s<=l&&r<=t) {
        seg[p]={k,k,0};
        pushdown(p);
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(s<=mid) modify1(p<<1,l,mid,s,t,k);
    if(mid<t) modify1(p<<1|1,mid+1,r,s,t,k);
    seg[p]=merge(seg[p<<1],seg[p<<1|1]);
    return;
}

void modify2(int p,int l,int r,int s,int t,int k) {
    if(s<=l&&r<=t) {
        pushdown(p);
        seg[p].mx+=k;
        seg[p].sum_tag+=k;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(s<=mid) modify2(p<<1,l,mid,s,t,k);
    if(mid<t) modify2(p<<1|1,mid+1,r,s,t,k);
    seg[p]=merge(seg[p<<1],seg[p<<1|1]);
    return;
}

node query(int p,int l,int r,int s,int t) {
    // cout<<p<<" "<<l<<" "<<r<<" "<<seg[p].mx<<endl;
    if(s<=l&&r<=t) return seg[p];
    pushdown(p);
    int mid=(l+r)>>1;
    node res={-NON,NON,0};
    if(s<=mid) res=merge(res,query(p<<1,l,mid,s,t));
    if(mid<t) res=merge(res,query(p<<1|1,mid+1,r,s,t));
    return res;
}

signed main() {
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++) {
        int op,l,r,x;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1) {
            scanf("%lld",&x);
            modify1(1,1,n,l,r,x);
        } else if(op==2) {
            scanf("%lld",&x);
            modify2(1,1,n,l,r,x);
        } else printf("%lld\n",query(1,1,n,l,r).mx);
    }

    return 0;
}

by steveyang137 @ 2024-07-20 10:58:49

@水星湖 红名大佬解释一下


by bulizuzupiyelodeduo @ 2024-07-20 11:04:41

if(s<=l&&r<=t) {
        seg[p]={k,k,0};
        pushdown(p);
        return;
    }
if(s<=l&&r<=t) {
        pushdown(p);
        seg[p].mx+=k;
        seg[p].sum_tag+=k;
        return;
    }

里调用pushdown会越界


by I_will_AKIOI @ 2024-07-20 11:08:50

线段树不是要开四倍空间吗?


by steveyang137 @ 2024-07-20 18:36:30

@I_will_AKIOI 仔细看我的seg开的是maxn<<2


by steveyang137 @ 2024-07-20 18:37:35

@taffy_official 有道理。那我特判叶子节点还是怎么


by steveyang137 @ 2024-07-20 19:30:20

@taffy_official 我糖了,到位置不用pushdown就行了。多谢!


|