就是收集了trick 。
线段树的扩展用法
- 单侧递归线段树
- 历史最大值线段树 (卢瑞恩)
- \(\text{Segment Tree Beats}\)
其中历史最大值线段树和 \(\text{Segment Tree Beats}\) 的历史最值操作可以结合。如果由区间修改操作会影响 \(\text{Segment Tree Beats}\) 的势能，具体的，每操作一次会让 \(O(\log^2n)\) 个区间的势能增加 \(O(1)\) ，所以时间复杂度将会多一个 \(\log n\) 。
- 历史版本和线段树 （维兹南与蘑菇）
关于区间 \(\text{mex}\)
我们定义一个区间 \([l,r]\) 为好的，当且仅当对于 \(\forall [L,R]\in [l,r)\cup (l,r],\text{mex}\{L,R\}\neq \text{mex}\{l,r\}\) 。那么可以证明，这样的区间数量在 \(2n\) 以内。(维兹南与蘑菇)
平面图与对偶图
- 平面图的最小割相当于对偶图的最短路 （小方的疑惑2）
竞赛图
-
竞赛图缩点之后是链状结构，每一个节点向之后强连通分量内的节点连边。
-
竞赛图的一个强连通分量内一定存在哈密顿回路（星际旅行）
-
竞赛图存在哈密顿路径
-
竞赛图存在哈密顿回路的要求是强连通。
-
竞赛图的三元环个数为 \(C_{n}^3-\sum C_{d_i}^2\) , \(d_i\) 为节点 \(i\) 的出度。（图图）
二分图
- 二分图存在完美匹配的条件是满足 \(\text{Hall}\) 定理。
其中对于 \(\text{Hall}\) 定理的定义是：假设二分图的左右部点分别为 \(U,V(|U|\leqslant |V|)\) ,如果对于 \(\forall S\in U,|S|\leqslant N(S)\) ，那么存在完美匹配。
\(\text{Hall}\) 定理的推广
-
如果要求匹配 \(>p\) ，那么要求 \(\forall S \in U,|S|-(|U|-p+1)\leqslant N(S)\)
-
如果匹配的条件是第 \(i\) 个左部点匹配 \(r_i\) 个右部点，那么要求 \(\forall S \in U ,\sum_{u\in S}r_u\leqslant N(S)\)