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 zhizhenyaohanyu @ 2024-08-20 15:58:25
@FIRESTARS 号难我不会
by FIRESTARS @ 2024-08-20 15:58:53
@zhizhenyaohanyu 那就别叫
by __F__ @ 2024-08-20 15:59:10
@FIRESTARS 火星弟弟快关我
by Deeplove_lzs @ 2024-08-20 15:59:18
和窝壶关
by zhizhenyaohanyu @ 2024-08-20 15:59:51
@FIRESTARS 我错了
by __crz_qaq__ @ 2024-08-20 16:00:10
@FIRESTARS 很久以前在某神秘地方写的
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5,inf=0x3f3f3f3f3f3f3f3f;
int n,m;
int tr[N<<2],tag[N<<2],upd[N<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p){tr[p]=max(tr[ls(p)],tr[rs(p)]);}
void addtag(int p,int pl,int pr,int d)
{
tr[p]+=d;
tag[p]+=d;
}
void addupd(int p,int pl,int pr,int d)
{
tag[p]=0;
tr[p]=d;
upd[p]=d;
}
void pushdown(int p,int pl,int pr)
{
int mid=pl+pr>>1;
if(upd[p]!=inf)
{
addupd(ls(p),pl,mid,upd[p]);
addupd(rs(p),mid+1,pr,upd[p]);
upd[p]=inf;
}
if(tag[p])
{
addtag(ls(p),pl,mid,tag[p]);
addtag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
}
}
void build(int p,int pl,int pr)
{
upd[p]=inf;tag[p]=0;
if(pl==pr)
{
cin>>tr[p];
return ;
}
int mid=pl+pr>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
pushup(p);
}
void add(int p,int pl,int pr,int L,int R,int d)
{
if(R<pl||pr<L)
return ;
if(L<=pl&&pr<=R)
{
addtag(p,pl,pr,d);
return ;
}
int mid=pl+pr>>1;
pushdown(p,pl,pr);
add(ls(p),pl,mid,L,R,d);
add(rs(p),mid+1,pr,L,R,d);
pushup(p);
}
void update(int p,int pl,int pr,int L,int R,int d)
{
if(R<pl||pr<L)
return ;
if(L<=pl&&pr<=R)
{
addupd(p,pl,pr,d);
return ;
}
int mid=pl+pr>>1;
pushdown(p,pl,pr);
update(ls(p),pl,mid,L,R,d);
update(rs(p),mid+1,pr,L,R,d);
pushup(p);
}
int query(int p,int pl,int pr,int L,int R)
{
if(R<pl||pr<L)
return -inf;
if(L<=pl&&pr<=R)
return tr[p];
int mid=pl+pr>>1;
pushdown(p,pl,pr);
return max(query(ls(p),pl,mid,L,R),query(rs(p),mid+1,pr,L,R));
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin>>n>>q;
build(1,1,n);
while(q--)
{
int op,l,r,x;
cin>>op>>l>>r;
if(op==1)
{
cin>>x;
update(1,1,n,l,r,x);
}
if(op==2)
{
cin>>x;
add(1,1,n,l,r,x);
}
if(op==3)
cout<<query(1,1,n,l,r)<<'\n';
}
}by FIRESTARS @ 2024-08-20 16:00:57
@F @chenyunxi1 那就先给我调好
by 违规用户名K&xs3Z^ @ 2024-08-20 16:01:57
@chenyunxi1 我看火星主页怎么显示已互关呀 不好意思不小心说出来了
by Deeplove_lzs @ 2024-08-20 16:02:34
@违规用户名K&xs3Z^
……
by _zuoqingyuan @ 2024-08-20 16:03:00
建议给 push_down单独写个函数