学习笔记 - 洛谷保存站

费用提前计算 dp：似乎没什么好记的？

长剖优化 dp：当状态与深度有关且树边长为 $1$ 时可以使用。时空复杂度 $O(n^2) \rightarrow O(n)$。

重剖优化 dp：当 dp 状态设置为 $f_{i,j}$ 时且只需要记录部分状态时，先遍历重儿子，再遍历轻儿子，在用到的时候分配内存，合并完后释放内存。有值的 dp 数组一定全在 $rt -u$ 的链上，发现只会在走轻边时贡献 $O(m)$ 的空间复杂度，轻边不超过 $O(\log n)$，于是总空间复杂度 $O(m\log n)$，但只能优化空间。~~作用有点太小了~~。

环上 dp：

1. 断环为链再倍长。

2. 讨论法。

3. 性质法。

基环树：

1. 边+树
 
2. 环+森林

例：

1. P5575拆环+森林，分讨左起第一个白点位置，预处理前缀信息。
2. agc004f二分图部分拆成环+森林，环上均分纸牌，非二分图部分拆成边+树。

圆方树（狭义）：处理仙人掌问题必备，对于每个环建立方点与每个环上的点连边。

广义圆方树：对于每个点双建立方点与每个点双内的点连边。

圆方树一定没有方方边，可以有圆方边和圆圆边（注：根据实现广义圆方树可以没有圆圆边）。

圆方树上 dp：分类转移，圆点到方点不转移，圆点到圆点转移一般与树相同，方点到圆点一般跑环形 dp。

$环+树=基环树\in仙人掌$

点双性质：（以下路径均为简单路径）

0. 点双上没有割点（定义）。

1. 任意两点间有两条不相交路径（最基本性质），也即过任意两点有简单环。

2. $\forall x\not=y\not=z,\exist x\to y$ 不经过点 $z$。

证明：若去掉点 $z$ 后两点不连通，则 $z$ 是割点，矛盾。

3. $\forall x,e$，过点 $x$ 和边 $e$有简单环（点双至少有三点）。

证明：将边 $e$ 拆成点，即 $u-X-v$ 形式，则点双性质不改变，此时由性质 $1$ 可得过 $X,x$ 有简单环。

4. $\forall x,y,e,x\to y$ 可以过 $e$。

证明：
- 只有两点的点双显然满足条件。

- 点数至少为 $3$ 的点双由性质 $3$ 有过 $x,e$ 的环。假设 $x\to y$ 一定不经过环上不为 $x$ 的点，那么此时去掉 $x$ 后 $e$ 与 $y$ 不连通，说明 $x$ 是割点，矛盾，所以必存在 $x\to y$ 过环上另外一点，此时若 $e$ 不在 $x\to y$ 上，则可以在环上绕另外一边过 $e$。

5. $\forall x\not=y\not=z,\exist x\to y$ 过点 $z$。

证明：对于点 $z$ 任意一条出边 $e$，由性质 $4$ 有 $x\to y$ 可以过 $e$，所以可以过$z$。

点双性质应用题：P8456

首先考虑容斥，将有黑有白的路径数替换为 $总点对数-只有全白路径点对数-只有全黑路径点对数-只有全黑或只有全白路径点对数$。

发现若两点路径所经过的点双内有黑边则路径可以不全白（设进入点为 $u$，离开点为 $v$，由性质 $4$ 则 $\exist u\to v$ 过黑边 $e$），反之同理。

对于最后一种，发现这两点一定在同一个点双内（若不在同一点双内，则路径 $x\to y$ 过某个割点 $z$，$x\to z$ 走全白，$z\to y$ 走全黑，则有黑有白）。

猜测每个点双内都有最多一个这样的点对。那么与这两个点 $x,y$ 相连的边一定有黑有白（显然）。假设有另一点 $z$ 满足与 $z$ 相连的边有黑有白，由性质 $4$ 可得存在 $x\to y$ 过 $z$ 的全白和全黑路径发现以 $z$ 为分界点，一半走全黑，一半走全白，则有黑有白，矛盾，所以存在 $x,y$ 时不存在 $z$ 是必要的。不存在 $z$ 时显然任意 $x\to y$ 全黑或全白。得证点双内存在一个这样的点对的充要条件是相连边有黑有白的点有且仅有 $2$ 个。

dp of dp:内层为判定性问题，外层为计数类问题。

一个有用的结论：对于值域为 $k$ 的树上最大独立集问题，有 $0\le max(g_{u,0},g_{u,1})-g_{u,0}\le k$。

插头dp:保存轮廓线上的状态和当前 $i,j$。

保存插头状态：最小表示法和括号匹配法。使用哈希表存储加速。

转移大力分讨。要求路径时记录特殊插头。要求单一路径时记录特殊插头凭空出现消失次数。

动态dp：对象带修的dp。
1. 对对象和转移的修改为 $O(1)$（或较小）级别。
2. 转移能够独立拆分。
3. 转移能写成广义矩阵乘法的形式。

最小增量法：如CF607B和CF1107E，在dp时不大量枚举，用较少的转移来包含所有转移方式。

广义决策单调性：dp式形如 $f_i=\min\limits_{j=1}^{i-1}f_j+w_{j+1,i}$,此时若满足 $w_{j+1,i+1}-w_{j+1,i}\le w_{j,i+1}-w_{j,i}$，即 $i$ 右移时，$j$ 大的增加得慢。此时决策点单调右移。移项可得到 $w_{j+1,i+1}+w_{i,j}\le w_{j+1,i}+w_{j,i+1}$，即四边形不等式的形式。

wqs二分：解决恰好选 $k$ 个且答案关于 $k$ 凸的问题。二分时需要注意三点共线。

凸函数的 $(min,+) (max,+)$ 卷积：等价于对凸包上的线段按斜率大小顺序进行归并。

对凸函数进行单点加，区间加转为斜率单点修，区间加等差数列转为斜率区间修。

用一条直线切两个凸函数卷积得到的凸函数，则切点横坐标等于分别切两个凸函数得到的切点横坐标之和。

树套树相关：

1. 主席树
2. TA+SGT
3. SGT+SGT
4. SGT+BST
5. BST+SGT
6. BST+BST

1&2：1只能静态，2可以动态。

2&3：2不能维护不可减信息，3可以。

3&4：4内部可以插入并维护顺序相关，而3不行。例如 $n$ 个队列每次在某个队列某个位置插入一个人，求队列区间中每个队列前 $k$ 个人的最大值。

3&5：5外部可以插入并维护顺序相关，而3不行。例如 $n$ 个队列每次在某两个队列间插入一个队列，求队列区间中每个队列前 $k$ 个人的最大值。

4&5：插入并维护顺序分别在内外层。

6：内外层都支持插入维护顺序。

区间逆序对的三维：

1. $i<j$
2. $a_i>a_j$
3. $l\le i,j\le r$

只限制 $i,j$ 中一个视为 $0.5$ 维。

SATT:LCT不能维护子树信息，原因是其没有子树结构。于是用splay维护原树虚儿子，并改为LCT整体结构为三叉树。在SATT中，对于实链左右儿子与LCT一致，虚儿子是虚儿子splay的根，实链splay根的父亲为所在实链链顶对应的虚点。虚儿子splay中顺序无意义，树形结构只是为了合并信息，虚儿子为对应实点所在实链splay的根。

[0]表示所在splay内子树信息。

余下信息有两种维护方式：

1. [1]表示当前点及虚儿子整个子树内信息。[2]表示当前点整个子树内信息。
2. [1]表示所在splay内子树内点的虚儿子整个子树内信息。

可以这样不区分实点虚点维护信息的原因是对于实点和虚点信息的具体意义是对称的。

KDT:有三种正确的维度循环方式：

1. $1\sim k$
2. 随机
3. 按方差最大的维度

动态KDT查询复杂度为 $O(\sum(\frac n{2^i})^{1-\frac1k})=O(n^{1-\frac1k})$

k大理论：找第 $k$ 优解，通过初始解来调整得到，主要问题是提前解锁和重复解锁。

树分块：

1. 直接按dfs序分块。

2. 按size分块，块数不能保证。

3. 撒点法

1. 随机撒点，直径和块长期望为 $S$，块数$\frac nS$。
   2. 从深度大的点开始找 $S$ 级祖先。
4. 王室联邦分块法：课后想了一下认为有使得每块连通且块大小不超过 $3B$ 的线性做法

等和卷积：$H_i=\sum_{i=0}^n F_iG_{n-i}$。直接FFT。

等差卷积：$H_i=\sum_{i=0}^{m-n} F_iG_{i+n}$。将 $G$ 逆序后转化为等和卷积。

KTT:线段树每个节点维护一个 $intr$，定义为最大的 $\Delta x$ 使得最大的一次函数一定不改变。发生交替时递归查找当前最大一次函数。原因：
  
  1. 最大的一次函数可能多次改变。
  2. 维护的 $intr<0$ 时最大一次函数可能不改变。

可以保证在查询时信息正确。可以理解为高阶 lazytag。KTT 中 lazytag 与普通 lazytag 的区别：

1. 只保证了最大一次函数正确。
  2. 个人对高阶的理解：

segbeats:

1. 区间最值操作：以 chmin 为例，此时有两种节点（$mx\le k$ 时操作无效果直接返回）：

1. $k\le mxx$，此时会减少区间内值的多样性，不超过$O(\sum len)=O(n\log n)$ 次。

2. $mxx<k<mx$，此时可以直接打标记。
2. 区间历史最值：标记的合并本质上是把父亲的操作序列接在儿子的操作序列后面。
     
    1. 历史最值：可以直接维护历史最值和历史标记最值。
    2. 历史版本和：考虑操作序列的拼接过程，需要注意特殊情况下父亲的操作序列开头可能会导致不同的拼接方式。

正在渲染内容...