Zerol's Notes
0%

Posted on Edited on In Disqus:

代码详见模板库。模板题 EOJ 3389-3393。

  • Q: 要不要把 n 补成 2 的幂？

  • A: 这个无所谓，但如果要写成自底向上，那么还是需要的，否则无法直接定位叶节点。

  • Q: pushdown 之后要不要立即 maintain？

  • A: 不用立即 maintain，但迟早是要的。但是立即 maintain 很可能会重复 maintain，增加超时风险。

  • Q:query 的时候要不要 pushdown？

  • A: 如果不要的话，查询时应该把之前访问到的结点的标签的效果累加起来，并作为参数递归下去。如果要的话，代码会更加具有普适性（比如 treap 只能选择 pushdown 标签，因为结点之间相对位置会改变）。

  • Q: maintain 的时候是否考虑当前结点的标签？

  • A: 都可以。如果考虑了，那么查询的时候就不要考虑当前结点的标签了，反之亦然。

  • Q: query 的时候先考虑 set 标签还是先考虑查询区间包含当前区间？

  • A: 都可以，但是先考虑 set 会快一些。

  • Q: 根节点是 0 还是 1？

  • A: 都可以，但好像 1 比较符合人性。

  • Q: 听说空间开三倍就够了？

  • A: 那可能就 GG 了，实测 4 倍是必要的。

其他注意事项：

  • maintain 函数要写得保证即便是重复调用也不会出错。
  • pushdown 子节点必须 maintain，尤其是那个没有递归下去的子节点。
  • 打完 set 标记后 add 标记必须清空。