警示后人
查看原帖
警示后人
232838
huangkx楼主2023/8/21 16:15

如果您用的是 LCT 写法:

  • “外界输入”可以不当成结点。
  • 一开始连边时可以全部都连虚边。
  • 要先用 DFS 或其他方法求出每个结点的 val。注意在此过程中并不满足父结点编号小于子结点。(参考第一篇题解)。
  • 在 Splay 上二分时要先考虑右子树,再考虑当前结点,最后考虑左子树。
  • 在 Splay 上二分时要注意判断当前结点时看 val[x](它自己的为 1 的子结点的个数) 而不是 f[x](它的子树中是不是全部都是 val 为 1 的结点)。(不过应该只有我会犯这种错)。
2023/8/21 16:15
加载中...