记录一些技巧

一半的半平面交

当求半平面交的一半(相当于求一个直线构成的下凸壳或上凸壳)时, 可以把如 $y=kx+b$ 的直线转化成 $(a, b)$ 求凸壳

长链剖分的换根说的是, 你做完长链剖分之后跑换根dp, 那么现在一个点有其长儿子的信息, 短儿子的信息和子树外的信息, 那么直接把所有短儿子都合并到子树外的信息上, 进入一个轻儿子的时候把自己删了, 把重儿子前 $h$ 个加入, 退出的时候撤销, 进入重儿子的时候就用全部的即可.

要求信息可合并, 可删, 且信息量是仅深度相关对.