FIRESTARS @ 2024-08-19 21:39:38
Rt,WA code：
#include<bits/stdc++.h>
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(tl>=l&&tr<=r)return t[v];
int tm=(tl+tr)/2;
if(b[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;
}
else if(b2[v]!=0)
{
t[v*2]+=b2[v]*(tm-tl+1);
t[v*2+1]+=b2[v]*(tr-tm);
b2[v*2]+=b2[v];
b2[v*2+1]+=b2[v];
b2[v]=0;
}
int s1=0,s2=0;
if(tm>=l)s1=getmax(v*2,tl,tm,l,r);
if(tm<r)s2=getmax(v*2+1,tm+1,tr,l,r);
return max(s1,s2);
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
if(l<=tl&&tr<=r)
{
t[v]=x;
vis[v]=1;b[v]=x;
return;
}
int tm=(tl+tr)/2;
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(b2[v]!=0)
{
t[v*2]=t[v*2]+b2[v*2];
t[v*2+1]=t[v*2+1]+b2[v*2+1];
b2[v*2]+=b2[v];
b2[v*2+1]+=b2[v];
b2[v]=0;
}
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]=t[v*2]+b2[v*2];
t[v*2+1]=t[v*2+1]+b2[v*2+1];
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);
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 chenxi2009 @ 2024-08-20 09:15:28
@FIRESTARS 建议变量名换一批容易看懂的
方便调试
好家伙把我拉下水了
by chenxi2009 @ 2024-08-20 09:42:24
A了 @FIRESTARS 你对着查一下
asn 是赋值标记，add 是加标记
优先级是先赋值后加
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000001],op,x,y,z,mx[4000001],asn[4000001],add[4000001];
int X = 1e18;
inline void pushup(int k){
mx[k] = max(mx[k << 1],mx[k << 1 | 1]);
return;
}
void build(int k,int l,int r){
if(l == r){
mx[k] = a[l];
return;
}
int mid = l + r >> 1;
build(k << 1,l,mid);
build(k << 1 | 1,mid + 1,r);
pushup(k);
return;
}
inline void pushdown(int k){
if(asn[k] != X){
asn[k << 1] = asn[k << 1 | 1] = mx[k << 1] = mx[k << 1 | 1] = asn[k];
add[k << 1] = add[k << 1 | 1] = 0;
}
else{
if(asn[k << 1] != X){
asn[k << 1] += add[k];
}
else{
add[k << 1] += add[k];
}
mx[k << 1] += add[k];
if(asn[k << 1 | 1] != X){
asn[k << 1 | 1] += add[k];
}
else{
add[k << 1 | 1] += add[k];
}
mx[k << 1 | 1] += add[k];
}
asn[k] = X,add[k] = 0;
return;
}
void cge(int k,int l,int r,int x,int y,int num){
if(y < l || x > r){
return;
}
if(x <= l && y >= r){
mx[k] = asn[k] = num;
add[k] = 0;
return;
}
if(asn[k] != X || add[k]){
pushdown(k);
}
int mid = l + r >> 1;
cge(k << 1,l,mid,x,y,num);
cge(k << 1 | 1,mid + 1,r,x,y,num);
pushup(k);
return;
}
void upd(int k,int l,int r,int x,int y,int num){
if(y < l || x > r){
return;
}
if(x <= l && y >= r){
if(asn[k] != X){
asn[k] += num;
}
else{
add[k] += num;
}
mx[k] += num;
return;
}
if(asn[k] != X || add[k]){
pushdown(k);
}
int mid = l + r >> 1;
upd(k << 1,l,mid,x,y,num);
upd(k << 1 | 1,mid + 1,r,x,y,num);
pushup(k);
return;
}
int ask(int k,int l,int r,int x,int y){
if(y < l || x > r){
return -1e18;
}
if(x <= l && y >= r){
return mx[k];
}
if(asn[k] != X || add[k]){
pushdown(k);
}
int mid = l + r >> 1;
return max(ask(k << 1,l,mid,x,y),ask(k << 1 | 1,mid + 1,r,x,y));
}
signed main(){
for(int i = 0;i <= 4000000;i ++){
asn[i] = X;
}
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 ++){
scanf("%lld",&op);
if(op == 1){
scanf("%lld%lld%lld",&x,&y,&z);
cge(1,1,n,x,y,z);
}
else if(op == 2){
scanf("%lld%lld%lld",&x,&y,&z);
upd(1,1,n,x,y,z);
}
else{
scanf("%lld%lld",&x,&y);
printf("%lld\n",ask(1,1,n,x,y));
}
}
return 0;
}by chenxi2009 @ 2024-08-20 09:45:56
@chenxi2009 刚刚WA掉是因为我下传的时候忘记考虑父节点具有 add 标记，子节点具有 asn 标记的情况了（我设定每个节点只会同时存在一种标记）
by FIRESTARS @ 2024-08-20 09:59:42
@chenxi2009 嗯，谢谢大佬