FIRESTARS @ 2024-08-20 15:57:20
WA了后4个点，求助
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005],t[4000005],vis[4000005],b[4000005],b2[4000005];
void build(int v,int tl,int tr)
{
if(tl==tr)
{
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=max(t[v*2],t[v*2+1]);
}
int getmax(int v,int tl,int tr,int l,int r)
{
if(tr < l || tl > r){
return -1e18;
}
if(vis[v]!=0)
{
t[v*2]=t[v];
t[v*2+1]=t[v];
b[v*2]=t[v];
b[v*2+1]=t[v];
vis[v]=b[v]=0;
}
if(tl>=l&&tr<=r)return t[v];
int tm=(tl+tr)/2;
if(b2[v]!=0)
{
t[v*2]+=b2[v];
t[v*2+1]+=b2[v];
b2[v*2]+=b2[v];
b2[v*2+1]+=b2[v];
b2[v]=0;
}
int ma=LLONG_MIN;
if(tm>=l)ma=max(ma,getmax(v*2,tl,tm,l,r));
if(tm<r)ma=max(ma,getmax(v*2+1,tm+1,tr,l,r));
return ma;
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
if(vis[v]!=0)
{
t[v*2]=b[v];
t[v*2+1]=b[v];
b[v*2]=b[v];
b[v*2+1]=b[v];
vis[v]=b[v]=0;
}
if(l<=tl&&tr<=r)
{
t[v]=x;
vis[v]=1;b[v]=x;
return;
}
if(b2[v]!=0)
b2[v]=0;
int tm=(tl+tr)/2;
if(tm>=l)updata(v*2,tl,tm,l,r,x);
if(tm<r)updata(v*2+1,tm+1,tr,l,r,x);
t[v]=max(t[v*2],t[v*2+1]);
return;
}
void updata2(int v,int tl,int tr,int l,int r,int x)
{
if(vis[v]!=0)
{
t[v*2]=b[v];
t[v*2+1]=b[v];
b[v*2]=b[v];
b[v*2+1]=b[v];
vis[v]=b[v]=0;
}
if(l<=tl&&tr<=r)
{
t[v]+=x;b2[v]+=x;
return;
}
int tm=(tl+tr)/2;
if(b2[v]!=0)
{
t[v*2]+=b2[v];
t[v*2+1]+=b2[v];
b2[v*2]+=b2[v];
b2[v*2+1]+=b2[v];
b2[v]=0;
}
if(tm>=l)updata2(v*2,tl,tm,l,r,x);
if(tm<r)updata2(v*2+1,tm+1,tr,l,r,x);
t[v]=max(t[v*2],t[v*2+1]);
return;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
// freopen("1.in","r",stdin);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(q--)
{
int opt,l,r,x;
cin>>opt;
if(opt==1)
{
cin>>l>>r>>x;
updata(1,1,n,l,r,x);
}
else if(opt==2)
{
cin>>l>>r>>x;
a[l]=r;
updata2(1,1,n,l,r,x);
}
else if(opt==3)
{
cin>>l>>r;
cout<<getmax(1,1,n,l,r)<<'\n';
}
}
}by __crz_qaq__ @ 2024-08-20 16:05:10
@FIRESTARS 神秘马蜂
by FIRESTARS @ 2024-08-20 16:06:56
@__crz_qaq__ c的tj
by zgzn @ 2024-08-20 16:12:05
@FIRESTARS 如果你觉得这没问题的话，建议long long……
by __crz_qaq__ @ 2024-08-20 16:12:49
@zgzn 眼角膜不要可以捐了
by zgzn @ 2024-08-20 16:13:47
@__crz_qaq__ 已捐
by FIRESTARS @ 2024-08-20 16:13:54
@__crz_qaq__ 可怜的狗狗跟陌生人说话要有礼貌懂不懂？
by __crz_qaq__ @ 2024-08-20 16:14:23
@FIRESTARS ？
by tangguo917 @ 2024-08-20 16:22:41
@FIRESTARS
#include<bits/stdc++.h>
#define int long long
#define ls(x) 2*x
#define rs(x) 2*x+1
using namespace std;
int a[1000005],t[8000005],vis[8000005],b[8000005],b2[8000005];
void build(int v,int tl,int tr)
{
b[v]=LLONG_MAX;
if(tl==tr)
{
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=max(t[v*2],t[v*2+1]);
}
void pushdown(int x) {
if(b[x]!=LLONG_MAX){
t[ls(x)]=b[x];
t[rs(x)]=b[x];
b[ls(x)]=b[x],b[rs(x)]=b[x];
b2[ls(x)]=b2[rs(x)]=0;
b[x]=LLONG_MAX;
}
t[ls(x)]+=b2[x];
t[rs(x)]+=b2[x];
b2[ls(x)]+=b2[x],b2[rs(x)]+=b2[x];
b2[x]=0;
}
int getmax(int v,int tl,int tr,int l,int r)
{
if(tl>=l&&tr<=r)return t[v];
int tm=(tl+tr)/2;
pushdown(v);
int ma=LLONG_MIN;
if(tm>=l)ma=max(ma,getmax(v*2,tl,tm,l,r));
if(tm<r)ma=max(ma,getmax(v*2+1,tm+1,tr,l,r));
return ma;
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
if(l<=tl&&tr<=r)
{
t[v]=x,b[v]=x,b2[v]=0;
return;
}
pushdown(v);
int tm=(tl+tr)/2;
if(tm>=l)updata(v*2,tl,tm,l,r,x);
if(tm<r)updata(v*2+1,tm+1,tr,l,r,x);
t[v]=max(t[v*2],t[v*2+1]);
return;
}
void updata2(int v,int tl,int tr,int l,int r,int x)
{
if(l<=tl&&tr<=r)
{
t[v]+=x,b2[v]+=x;
return;
}
int tm=(tl+tr)/2;
pushdown(v);
if(tm>=l)updata2(v*2,tl,tm,l,r,x);
if(tm<r)updata2(v*2+1,tm+1,tr,l,r,x);
t[v]=max(t[v*2],t[v*2+1]);
return;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(q--)
{
int opt,l,r,x;
cin>>opt;
if(opt==1)
{
cin>>l>>r>>x;
updata(1,1,n,l,r,x);
}
else if(opt==2)
{
cin>>l>>r>>x;
updata2(1,1,n,l,r,x);
}
else if(opt==3)
{
cin>>l>>r;
cout<<getmax(1,1,n,l,r)<<'\n';
}
}
}pushdown搞成了函数，是标记覆盖的问题
by FIRESTARS @ 2024-08-20 16:25:58
@tangguo917 谢谢！
by FIRESTARS @ 2024-08-20 16:26:24
@tangguo917 已关，可以壶关吗QwQ