-
连续段 Dp
连续段 Dp简介求个满足条件的排列数个数，存在一些例如 的限制条件 假如我们记录哪些数出现过，那么显然状态会爆炸，无法记录 我们可以从大到小，或从小到大来填数 状态转移的过程可能与相邻的已插入元素的具体信息相关，如插入一个新元素时，需要知道与其插入位置相邻的两个元素的值是多少 推荐文章 基本操作它的元素插入操作只会在连续段的两端进行，通过新建连续段，插入至已有连续段的两端，合并两连续段三类... -
斜率优化 Dp
斜率优化 介绍一般为 等降掉一个 的 优化 本质上基于决策单调性，单调队列维护 方程大概长成： 注： 为常数 https://www.cnblogs.com/MashiroSky/p/6009685.html https://www.cnblogs.com/Xing-Ling/p/11210179.html StepP3195 [HNOI2008] 玩具装箱 例题 朴素 化... -
cdq 分治
Here’s something encrypted, password is required to continue reading.
-
Dfn序 && 欧拉序
Dfn 序 点修改+子树查询/子树修改+点查询 树状数组维护单点/差分 子树修改+子树查询 线段树区间加区间和 路径修改+点查询 维护 和每个点到根的路径和，转成 ，，， 从下往上差分，一个点的差分为它的值-所有儿子的值 1234mdf(dfn[x],d);mdf(dfn[y],d);mdf(dfn[p],-d);if(fa[p]) mdf(dfn[fa[p]],-d);pri... -
Extra 线段树-优化建图
常见线段树 一般是区间/点向区间/点连边 线段树的本质就是区间向点的映射，我们利用这一点优化 P6348 [PA2011] Journeys 我们建立一颗入树和出树，如下图 左边是出树， 右边是入树， 蓝色边权为 当我们需要从 建边，就 对 建立两个虚点，虚点之间连边 1234567891011121314151617181920212223242526272829303132... -
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(j)) a[i][j]+=v;} 12345678910111213int sum(int x,int y){ int res=0... -
树剖
树链剖分将树上问题转到序列上，转而方便用数据结构维护 重子节点：表示其子节点中子树最大的子结点 如果有多个子树最大的子结点，取其一 如果没有子节点，就无重子节点 轻子节点：表示剩余的所有子结点 重边：从这个结点到重子节点的边为 轻边：到其他轻子节点的边为 重链：若干条首尾衔接的重边构成 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链 树上每个节点都属于且仅属于一条重链 在剖分时，重... -
三分
三分法求单峰函数极值点，当发现类似双指针的结构最值时，可以考虑三分 https://blog.csdn.net/Mr_dimple/article/details/126361376 实数三分例题 https://www.luogu.com.cn/problem/P3382 给出一个 次函数，保证在范围 内存在一点 ，使得 上单调增， 上单调减。试求出 的值 时， 就没用了，这就... -
线性代数
Here’s something encrypted, password is required to continue reading.
-
EXSTL-Pbds
奇淫巧技-Pbds 的平衡树+ 表 内部为平衡树 平衡树有红黑树，，有序向量树 一般就用红黑树 123#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds; 一般就定义成 1tree<int,null_type...
