杂记

Tarjan 求LCA

• 已经访问过的点在当前点子树里，代表元一定是当前点（回溯于此）
• 已经访问的点不在当前点子树里，代表元一定是当前点祖先（反证法）
• 已经访问的点的代表元为最近的祖先（反证，若不是则已经回溯到这个点这俩成同一代表元）

欧拉序求LCA

同tarjan，进来记录一次，再次出发记录\(n\)次，出来记录一次，形成一个序列

• 第一次出现和最后一次出现间的点全部为后代

• 若不互为祖先：形如\(.lca..a.a.a.a..lca..lca..lca..b.b.b.b..lca.\)，\(a\)最后一次出现到\(b\)第一次出现之间会出现一个\(a,b\)的祖先，且只出现一个（不会出现更上一级的祖先因为\(b\)还没遍历）

• 若互为祖先\(a...a...b...b...a...a\),\(a\)和\(b\)之间夹杂的全为\(a\)的后代，深度较深

所以找\([euler_{a_1},euler_{b_1}]\)中的深度最小点即可

二分

\(a\)升高则\(b\)升高，而且\(b\)好判断，于是二分\(a\).

欧拉回路

注意到，一次一直走下去一定是一条回路的性质，然后在回溯中可以拆为多条回路然后靠回溯拼接起来

• 一次小回溯结束是一条回路
• 每个大回溯主分支是回路但有多个小回溯分支
• 当大回溯时：大回溯前半+小回溯路径+大回溯后半
• 大回溯也是一条回路
• 保证每个回溯都是一条回路最后合并到一条回路上
• 这条回路为欧拉回路

无向图和有向图均适应

半欧拉图的欧拉路径

• 第一次走的分支就能从起点走到终点（反证法）
• 之后从中延申出来的都是环了（因为此时无奇数点）
• 合并进去
• 依旧回溯得到欧拉路径

无向图有向图均适用

关于单调栈和单调队列

将之后不可能作为答案的元素pop，然后刚好可以有符合答案的元素。

差分

前缀和的逆运算，求差分就假设原数组是前缀和，求原数组就是求前缀和。

二维的就是 $$ a_{i,j}=s_{i,j}-s_{i-1,j}-s_{i,j-1}+s_{i-1,j-1} $$ 由于差分数组一个发生改变会影响到后面所有原数组，所以可以用于区间修改