已AC 但是mxqz线段树玄学问题

P1253 扶苏的问题

Xeqwq @ 2022-04-09 22:18:13

1.为什么Maxn开1e6+5不过,开1e6+2e5过(之前有帖子发过 是不是数据的锅
2.为什么去掉我代码main函数中那个初始化be标记的那行会wa20分

#include <iostream>
using namespace std;
typedef long long ll;
inline ll lc(ll p){return p<<1;}
inline ll rc(ll p){return (p<<1)|1;}
ll n,q;
const ll Maxn=1e6+2e5,inf=0x3f3f3f3f3f3f3f3f;
ll a[Maxn],dat[Maxn*4],add[Maxn*4],be[Maxn*4];
void pushup(ll p)
{
    dat[p]=max(dat[lc(p)],dat[rc(p)]);
}
void build(ll p,ll l,ll r)
{
    if(l==r)
    {
        dat[p]=a[l];
        be[p]=inf;
        return;
    }
    ll mid=(l+r)>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    pushup(p);
}
void movetag_Be(ll p)
{
    if(be[p]!=inf)
    {
        add[lc(p)]=add[rc(p)]=0;
        dat[lc(p)]=dat[rc(p)]=be[lc(p)]=be[rc(p)]=be[p];
        be[p]=inf;
    }
}
void movetag_Add(ll p)
{
    if(add[p]!=0)
    {
        movetag_Be(p);
        dat[lc(p)]+=add[p];
        dat[rc(p)]+=add[p];
        add[lc(p)]+=add[p];
        add[rc(p)]+=add[p];
        add[p]=0;
    }
}
void Add(ll p,ll l,ll r,ll ql,ll qr,ll d)
{
    if(ql<=l&&qr>=r)
    {
        movetag_Be(p);
        add[p]+=d;
        dat[p]+=d;
        return;
    }
    movetag_Be(p);
    movetag_Add(p);
    ll mid=(l+r)>>1;
    if(ql<=mid) Add(lc(p),l,mid,ql,qr,d);
    if(qr>mid) Add(rc(p),mid+1,r,ql,qr,d);
    pushup(p);
}
void Be(ll p,ll l,ll r,ll ql,ll qr,ll d)
{
    if(ql<=l&&qr>=r)
    {
        add[p]=0;
        dat[p]=be[p]=d;
        return;
    }
    movetag_Be(p);
    movetag_Add(p);
    ll mid=(l+r)>>1;
    if(ql<=mid) Be(lc(p),l,mid,ql,qr,d);
    if(qr>mid) Be(rc(p),mid+1,r,ql,qr,d);
    pushup(p);
}
ll query(ll p,ll l,ll r,ll ql,ll qr)
{
    if(ql<=l&&qr>=r) return dat[p];
    movetag_Be(p);
    movetag_Add(p);
    ll mid=(l+r)>>1;
    ll ans=-inf;
    if(ql<=mid) ans=max(ans,query(lc(p),l,mid,ql,qr));
    if(qr>mid) ans=max(ans,query(rc(p),mid+1,r,ql,qr));
    return ans;
}

signed main()
{
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<=4*Maxn;i++) be[i]=inf;
    build(1,1,n);
    ll op,x,y,k;
    while(q--)
    {
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)
        {
            scanf("%lld",&k);
            Be(1,1,n,x,y,k);
        }
        else if(op==2)
        {
            scanf("%lld",&k);
            Add(1,1,n,x,y,k);
        }
        else
            printf("%lld\n",query(1,1,n,x,y)); 
    }
    return 0;
}

by Xeqwq @ 2022-04-09 22:18:39

be和add都是标记


by Dr_Gilbert @ 2022-04-09 22:23:56

@整活队长xeq

  1. 数据无锅,我开 10^6 可以通过,建议检查一下你的代码
  2. 应该在操作前将所有节点的 be 设为无穷大,而你的 build() 函数里只将叶子节点的 be 设为了无穷大,所以会 WA

by Xeqwq @ 2022-04-09 22:26:32

@Dr_Gilbert 明白了 感谢巨神!


by Xeqwq @ 2022-04-09 22:26:48

此贴终


|