搜集了讨论区出现的一些常见错误,加上我个人犯的错误,整理而成的快速检查清单:
pushdown 部分:
- 左右儿子的标记也需更新
- 注意标记的下放顺序:区间已经有推平时,下放翻转标记则需把推平标记异或 1;如果区间已经存在翻转标记,下放推平标记时则需清空翻转标记,翻转时要么改推平标记要么改翻转标记,不要两者都改
- 如果你的推平标记初始值是非零的(例如我设置成 −1),那么在判断是否存在推平标记时不能使用
if (tree[idx].tag) 这样的语句,而是 if (tree[idx].tag >= 0)(−1 也会返回 true)
- 注意区间翻转交换的是同一个子树同一个方向上 0 和 1 的最大连续数。
- 标记是异或,不要赋值成 1
pushup 部分:
- 如果你做维护最大子段和的题做多了,请注意此处维护区间最长左/右连续数量时需要判断能否跨区间合并(如果你的最大连续数查询函数返回一个线段树,那么查询维护过程同理)
数值查询部分:
- 开头需要
pushdown
- 如果你查询
1 的个数时选择返回数字,那么请用 if (l <= mid) return findLeft 的形式;如果你查询最大连续数量时返回一个线段树结构体,那么请用 if (l > mid) return findRight
区间修改部分:
- 开头需要
pushdown
- 当前区间被完全包含,需要给当前编号打标记,同时更新当前的信息,并
return
- 结尾需
pushup
建树部分:
- 不要忘记维护两种数的最大连续长度,把所有信息维护完
- 不要忘了
return
- 如果你使用结构体存储左右节点的下标,注意
mid 的计算方式可能略有不同
主函数/全局定义部分:
- 线段树开四倍空间
- 操作时读入的下标从 0 开始
- 不要忘记
build
- 最好把标记分开存
祝AC