算法复习计划：

  • [ ] 最大流
  • [X] 点分治
  • [ ] 可持久化线段树
  • [X] 后缀自动机(maybe)
  • [ ] LCT
  • [ ] 文艺平衡树&可持久化（文艺）平衡树
  • [ ] 树链剖分
  • [ ] 莫队
  • [ ] 分块
  • [ ] 2-sat
  • [ ] Tarjan
  • [ ] 珂朵莉树
  • [ ] CDQ分治
  • [ ] 整体二分
  • [ ] 左偏树
  • [ ] AC自动机
  • [ ] 莫反

新(?)算法：

  • [ ] DP
  • [ ] 根号分治
  • [ ] 费用流
  • [ ] 圆方树
  • [ ] 虚树
  • [ ] 李超线段树
  • [ ] 数论

笔记：

1. 关于点分治的复杂度

由于中心的子树大小不会超过整棵树的一半，故处理到一个点时是在至多 log⁡n\log n 次 dfs 遍历其之后处理到，故每个点至多遍历 log⁡n\log n 次，复杂度为 nlog⁡nn\log n.

此外特别注意，由于此复杂度，对每个子树的容斥，计算必须与子树大小严格挂钩，否则会出现 nknk 等复杂度（见 P4149 [IOI2011] Race）