steveyang137 @ 2024-07-20 10:57:53
如题,n应该最大只有1e6啊,为什么需要开到更大呢
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int MAXN=2e6+5,NON=1e18+1;
int n,q;
struct node {
int mx,cover_tag,sum_tag;
} seg[MAXN<<2];
int a[MAXN];
node merge(node s1,node s2) {
node s3;
s3.mx=max(s1.mx,s2.mx);
s3.cover_tag=NON;
s3.sum_tag=0;
return s3;
}
void build(int p,int l,int r) {
if(l==r) {
seg[p].mx=a[l];
seg[p].cover_tag=NON;
seg[p].sum_tag=0;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
seg[p]=merge(seg[p<<1],seg[p<<1|1]);
return;
}
void pushdown(int p) {
if(seg[p].cover_tag!=NON) {
seg[p<<1].cover_tag=seg[p<<1|1].cover_tag=seg[p].cover_tag;
seg[p<<1].mx=seg[p<<1|1].mx=seg[p].mx;
seg[p<<1].sum_tag=seg[p<<1|1].sum_tag=0;
seg[p].cover_tag=NON;
seg[p].sum_tag=0;
}
if(seg[p].sum_tag) {
seg[p<<1].mx+=seg[p].sum_tag;
seg[p<<1|1].mx+=seg[p].sum_tag;
seg[p<<1].sum_tag+=seg[p].sum_tag;
seg[p<<1|1].sum_tag+=seg[p].sum_tag;
seg[p].sum_tag=0;
}
// cout<<p<<":"<<seg[p].mx<<endl;
return;
}
void modify1(int p,int l,int r,int s,int t,int k) {
if(s<=l&&r<=t) {
seg[p]={k,k,0};
pushdown(p);
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(s<=mid) modify1(p<<1,l,mid,s,t,k);
if(mid<t) modify1(p<<1|1,mid+1,r,s,t,k);
seg[p]=merge(seg[p<<1],seg[p<<1|1]);
return;
}
void modify2(int p,int l,int r,int s,int t,int k) {
if(s<=l&&r<=t) {
pushdown(p);
seg[p].mx+=k;
seg[p].sum_tag+=k;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(s<=mid) modify2(p<<1,l,mid,s,t,k);
if(mid<t) modify2(p<<1|1,mid+1,r,s,t,k);
seg[p]=merge(seg[p<<1],seg[p<<1|1]);
return;
}
node query(int p,int l,int r,int s,int t) {
// cout<<p<<" "<<l<<" "<<r<<" "<<seg[p].mx<<endl;
if(s<=l&&r<=t) return seg[p];
pushdown(p);
int mid=(l+r)>>1;
node res={-NON,NON,0};
if(s<=mid) res=merge(res,query(p<<1,l,mid,s,t));
if(mid<t) res=merge(res,query(p<<1|1,mid+1,r,s,t));
return res;
}
signed main() {
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++) {
int op,l,r,x;
scanf("%lld%lld%lld",&op,&l,&r);
if(op==1) {
scanf("%lld",&x);
modify1(1,1,n,l,r,x);
} else if(op==2) {
scanf("%lld",&x);
modify2(1,1,n,l,r,x);
} else printf("%lld\n",query(1,1,n,l,r).mx);
}
return 0;
}
by steveyang137 @ 2024-07-20 10:58:49
@水星湖 红名大佬解释一下
by bulizuzupiyelodeduo @ 2024-07-20 11:04:41
if(s<=l&&r<=t) {
seg[p]={k,k,0};
pushdown(p);
return;
}
if(s<=l&&r<=t) {
pushdown(p);
seg[p].mx+=k;
seg[p].sum_tag+=k;
return;
}
里调用pushdown会越界
by I_will_AKIOI @ 2024-07-20 11:08:50
线段树不是要开四倍空间吗?
by steveyang137 @ 2024-07-20 18:36:30
@I_will_AKIOI 仔细看我的seg开的是maxn<<2
by steveyang137 @ 2024-07-20 18:37:35
@taffy_official 有道理。那我特判叶子节点还是怎么
by steveyang137 @ 2024-07-20 19:30:20
@taffy_official 我糖了,到位置不用pushdown就行了。多谢!