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
build()
函数里只将叶子节点的 WA
by Xeqwq @ 2022-04-09 22:26:32
@Dr_Gilbert 明白了 感谢巨神!
by Xeqwq @ 2022-04-09 22:26:48
此贴终