-
斜率优化 Dp
斜率优化 $dp$ 介绍 一般为 $O(n^3) \to O(n^2)$ 等降掉一个 $O(n)$ 的 $dp$ 优化 本质上基于决策单调性，单调队列维护 $dp$ 方程大概长成： $$f_i=\min_{j=0}{i-1},or,\max_{j=0... -
cdq 分治
Here’s something encrypted, password is required to continue reading.
-
Dfn序 && 欧拉序
Dfn 序 点修改+子树查询/子树修改+点查询 树状数组维护单点/差分 子树修改+子树查询 线段树区间加区间和 路径修改+点查询 维护 $lca$ 和每个点到根的路径和，转成 $u \to rt$，$v \to rt$，$lca \to ... -
Extra 线段树-优化建图
常见线段树 $trick$ 一般是区间/点向区间/点连边 线段树的本质就是区间向点的映射，我们利用这一点优化 P6348 [PA2011] Journeys 我们建立一颗入树和出树，如下图 左边是出树， 右边是入树， 蓝色边权为 $0$ 当我们需... -
Extra 树状数组
单点加+矩阵求和 123456void add(int x,int y,int v){ for (int i=x;i<=n;i+=lowbit(i)) for (int j=y;j<=m;j+=lowbit(... -
树剖
树链剖分 将树上问题转到序列上，转而方便用数据结构维护 重子节点：表示其子节点中子树最大的子结点 如果有多个子树最大的子结点，取其一 如果没有子节点，就无重子节点 轻子节点：表示剩余的所有子结点 重边：从这个结点到重子节点的边为 轻边：到其他轻子节点... -
三分
三分法 求单峰函数极值点，当发现类似双指针的结构最值时，可以考虑三分 https://blog.csdn.net/Mr_dimple/article/details/126361376 ?实数三分 例题 https://www.luogu.com.... -
线性代数
Here’s something encrypted, password is required to continue reading.
-
EXSTL-Pbds
奇淫巧技-Pbds $stl$ 的平衡树+ $hash$ 表 内部为平衡树 平衡树有红黑树，$Splay$，有序向量树 一般就用红黑树 123#include<ext/pb_ds/assoc_container.hpp>#include&... -
EXSTL-Rope
奇淫巧技-Rope $stl$ 的可持久化平衡树，无法做区间第 $k$ 大 内部为块状链表实现 12345678910111213141516#include <ext/rope>using namespace __gnu_cxx;rop...