线段树经典例题 40pts 求助大佬

P1253 扶苏的问题

cat_lover1 @ 2023-11-15 21:14:36

//integer may be negative,so Read() should be noticed
max(a,b){return a>b?a:b;}
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y//important
tr[4000001],lzy1[4000001],lzy2[4000001];
void Pushup(h){tr[h]=max(tr[lc],tr[rc]);}
void Pushdown(h){
  if(lzy1[h]){
    lzy1[lc]=lzy1[rc]=lzy1[h],lzy2[lc]=lzy2[rc]=lzy2[h];
    tr[lc]=tr[rc]=lzy1[h]+lzy2[h];
  }
  else if(lzy2[h]){
    lzy2[lc]+=lzy2[h],lzy2[rc]+=lzy2[h];
    tr[lc]+=lzy2[h],tr[rc]+=lzy2[h];
  }
  lzy1[h]=lzy2[h]=0;
}
void Build(h,l,r){
  //printf("Build:[h=%d,l=%d,r=%d]\n",h,l,r);
  if(l==r){scanf("%d",tr+h);return;}
  Build(lc,l,mid),Build(rc,mid+1,r);
  Pushup(h);
}
Query(h,l,r,x,y){
  //printf("Query:[h=%d,l=%d,r=%d,x=%d,y=%d]\n",h,l,r,x,y);
  if(IN)return tr[h];
  Pushdown(h);
  if(y<=mid)return Query(lc,l,mid,x,y);
  if(x>mid)return Query(rc,mid+1,r,x,y);
  return max(Query(lc,l,mid,x,y),Query(rc,mid+1,r,x,y));
}
void Modify(h,l,r,x,y,k){
  //printf("Modify:[h=%d,l=%d,r=%d,x=%d,y=%d,k=%d]\n",h,l,r,x,y,k);
  if(IN){tr[h]=k;lzy1[h]=k,lzy2[h]=0;return;}
  Pushdown(h);
      if(y<=mid)Modify(lc,l,mid,x,y,k);
  else if(x>mid)Modify(rc,mid+1,r,x,y,k);
  else Modify(lc,l,mid,x,y,k),Modify(rc,mid+1,r,x,y,k);
  Pushup(h);
}                            
void Update(h,l,r,x,y,k){
  //printf("Update:[h=%d,l=%d,r=%d,x=%d,y=%d,k=%d]\n",h,l,r,x,y,k);
  if(IN){tr[h]+=k;lzy2[h]+=k;return;}
  Pushdown(h);
      if(y<=mid)Update(lc,l,mid,x,y,k);
  else if(x>mid)Update(rc,mid+1,r,x,y,k);
  else Update(lc,l,mid,x,y,k),Update(rc,mid+1,r,x,y,k);
  Pushup(h);
}
main(){
  int n,q;scanf("%d%d",&n,&q);
  Build(1,1,n);
  while(q--){
    int op,x,y;scanf("%d%d%d",&op,&x,&y);
         if(op==1){int z;scanf("%d",&z);Modify(1,1,n,x,y,z);}
    else if(op==2){int z;scanf("%d",&z);Update(1,1,n,x,y,z);}
    else if(op==3)printf("%d\n",Query(1,1,n,x,y));
  }
}

by Shirley_ninefish @ 2023-11-15 21:34:51

@cz_awa 你这样的话,如果区间覆盖为0,那不就没法向下传递懒标记了吗


by Shirley_ninefish @ 2023-11-15 21:42:10

你可以定义一个不在-1e9~1e9范围内的inf,初始化和清空时都让lzy1=inf,在pushdown的时候就判断lzy1是否等于inf,等于则表示没被标记,否则下传


by cat_lover1 @ 2023-11-15 22:21:25

@Shirley_ninefish 明白了,感谢大佬 :)


by cat_lover1 @ 2023-11-15 22:31:12

@Shirley_ninefish 我加入了一个bool数组来判断是否需要更改lzy1,但只是50分


_Bool pd1[4000001];

void Pushdown(h){
  if(pd1[h])
   ...
}
void Modify(){
  if(IN){tr[h]=k;pd1[h]=1,lzy1[h]=k,lzy2[h]=0;return;}
  ...
}

by GXYZY @ 2023-11-15 22:33:12

@cz_awa 同问,我也是加了一个bool,但是也是50分


by cat_lover1 @ 2023-11-15 22:34:18

我再调调


by Shirley_ninefish @ 2023-11-16 07:35:58

@cz_awa emmm,你开了 long long 吗?


by Shirley_ninefish @ 2023-11-16 08:04:32

我试了一下你的代码,其他地方好像没什么问题,看起来应该就是没开 long long 的问题qwq


by cat_lover1 @ 2023-11-16 11:27:59

@Shirley_ninefish 感恩大佬,祝你NOIP rp++ 是的,就是long long的锅,我已经ac了


|