蓝书坑害蒟蒻!
  • 板块学术版
  • 楼主shiroko2008
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/8/2 14:33
  • 上次更新2023/10/27 17:22:41
查看原帖
蓝书坑害蒟蒻!
543206
shiroko2008楼主2022/8/2 14:33

上午打线段树板子,对着蓝书打只有30pts,调了两个小时发现,蓝书上的maintain函数

void maintain (int o,int l,int r) {
	int lc=o*2,rc=o*2+1;
	if (r>l) {
		sumv[o]=sumv[lc]+sumv[rc];
		minv[o]=min(minv[lc],minv[rc]);
		maxv[o]=max(maxv[lc],maxv[rc]);
	}
	minv[o]+=addv[o];
	maxv[o]+=addv[o];
	sumv[o]+=addv[o]*(r-l+1);
}

没有特判叶子结点

else sumv[o]=minv[o]=maxv[o]=val[l];

,导致叶子节点的懒标记被重复累加

退钱!!1

2022/8/2 14:33
加载中...