想把 OI 中的方法论总结一下，包括一些常见套路和有意思的 idea，并包括深度理解。
矩阵乘法
矩阵乘法主要用于优化数列或状态的递推。设矩阵大小为 $n\times n$，那么求 $T$ 时刻的局面就是 $\mathcal{O}(n^3\log T)$。如果有 $q$ 次询问，可以预处理所有 $2$ 的整数次幂的矩阵，然后采用一维向量乘矩阵得到答案，复杂度从 $\mathcal{O}(qn^3\log T)$ 优化至 $\mathcal{O}(n^3\log T+qn^2\log T)$。
注意矩阵乘法优化 $dp$ 要保证每个阶段的转移形式完全相同。
运算形式
矩阵乘法一般是两种运算形式叠加使用，记运算符号 $mat(\times,+)$ 的转移形式为：
$res.num_{i,j}+=num_{i,k}\times A.num_{j,k}$
对于运算符号有如下要求：
- 第一种运算满足交换律；
- 第一种运算满足结合律；
- 第一种对第二种运算满足分配率。
下面列举几种常见符号组合。
$mat(\times,+)$：路径计数
$mat(+,\max)$：最长路
$mat(+,\min)$：最短路
$mat(\text{&},|)$：判图连通
题面形式
状态很少 $(n-300)$，最终所求数列的项数很大 $(T-10^{18})$，每个位置的转移方式相同，比如有递推公式或对于每个阶段固定的转移方程。
P1613 跑路 $n\le 50,T\le 10^{18}$ ，且每个点的转移方式相同，用 $mat(\text{&},|)$ 判是否连通，然后跑 floyd。
P6569 [NOI Online #3 提高组] 魔法值 $n\le100,T\le 2^{32}$，对于每个点的转移，在每一个时刻都只跟它周围点的状态有关，记 $mat_{u,v}$ 表示 $u,v$ 之间是否有边，有边为 $1$，没边为 $0$，写一个 $mat(\text{&},\oplus)$ 矩阵运算再用 $2$ 的整数次幂预处理矩阵优化询问即可。
P6772 [NOI2020] 美食家 拆点构建矩阵，用 $mat(\times,\max)$ 运算，时间复杂度 $O((5n)^3\log T)$。
排序
排序的本质：交换逆序对的过程。
一个位置可以被“排序”的充分必要条件：存在关于这个位置的逆序对。
CF1136D Nastya Is Buying Lunch 可以看作每一对 $(u,v)$ 都是一对可进行相邻交换的逆序对，找到最后一个人 $x$ 能够交换的逆序对 $(y,x)$，当且仅当 $y\sim x$ 之间的一段前缀（可以为空）是 $y$ 的逆序对，后缀（可以为空）是 $x$ 的逆序对，否则就会成为一个对 $y$ 之前的元素的一个阻碍。
CF1187D Subarray Sorting 考虑 $A$ 换到 $B$ 的充分必要条件。（往往这一步最难）我们去考虑排序的本质，能删逆序对，那么如果 $B$ 存在的逆序对 $A$ 中没有，那么 $A$ 就不能加逆序对到 $B$，那么这就是 YES 的一个必要条件。充分性的证明即我们是否能对于上述情况，能否找到一个操作保证换掉 $B$ 中没出现的逆序对。考虑一种操作方案：从后往前做，对于当前的数，做一遍冒泡排序消除所有不在 $B$ 的逆序对。
所以我们考虑是否会出现这样一种情况：是否在当前的数后有一个位置构成的逆序对出现在 $B$，但之后又出现了一个不出现在 $B$ 的逆序对？（也就是我必须先消除前面在 $B$ 的逆序对，才能消除后面不在 $B$ 的逆序对从而不合法，如果不存在这种情况，那么冒泡就是对的）
首先，不妨设当前的数为 $x$，后面那个出现在 $B$ 中的逆序对为 $y$，不出现在 $B$ 中的逆序对为 $z$，也就是如下的一种局面：
不难发现，当且仅当 $y<z<x$ 时不能采用上述做法，但是最后我们要排成 $z-x-y$ 的形式，这样我们就多了一个 $(z,y)$ 逆序对，所以这种在必要的时候就被判掉了。那么我们也成功的说明了上述的必要条件有恰当的构造方法使得称为 $B$ 序列，变为了充分必要条件，至于最后的判断，属于技术问题，留作口胡。（提示：对于一个数 $x$ 维护其后面的逆序对集是否包含于这个数在 $B$ 中对应的逆序对集）
插旗法
可以对于一个环上顺序置换最优解问题，从 $n$ 个人到 $n$ 个位置的问题转化成了 $n$ 个旗子到 $1$ 个位置的问题。
由于不同的环只有 $2n$ 个，枚举每种环，考虑有多少人不在最终局面的位置上，所有取最小即可，复杂度 $\mathcal{O}(n^2)$。
我们不妨考虑，其实就是对于所有情况最小化初始局面和最终局面不在同一位置的人数。如果顺时针和逆时针分开考虑的话，其实就是 $n$ 个循环移位，循环移位不改变任意两点的相对位置，所以有了插旗法：首先我们找到 $1$ 的位置是对的最终局面，记为 $P$，然后看每个人从初始局面顺时针走多少步能走到最终局面的对应位置，然后我们就对这个步数的下标查一个旗，表示 $P$ 这个排列顺时针移动一定次数就会让这个插旗的人产生贡献，最后插旗最多的地方即为最优的最终局面，复杂度 $\mathcal{O}(n)$。
这题还是从初始局面转移到 $2n$ 个最终局面的最优，先考虑顺时针，我们固定 $1$ 的初始位置就是最终局面的位置，记这个局面为 $P$，然后我们在 $i$ 后面 $(i-1)$ 个位置插一个旗，然后想象 $i$ 和旗子一块移动，这样达到最终局面后，所有旗子都到达了 $1$ 位置，现在我们就转化成了所有旗子到某个位置的最小总距离。（因为旗子的位置是与 $1$ 的相对位置，而 $1$ 的位置 $n$ 种任选）
这个有个贪心做法：枚举一个位置把圆切成两边，发现一定是把旗子都切在一边，所以就是把最长段给扔了。
时间复杂度 $\mathcal{O}(n)$。
置换排序模型
对于一个置换 $p$，以 $i\rightarrow p_i$ 连边，那么就是 $n$ 点 $n$ 边，且每点入度出度均为 $1$，也就是由若干个环组成的图。
考虑对于一个置换，最终的有序状态是 $n$ 个自环，而一次交换可以从一个环拿出一个数使其变为自环，那么操作数即为 $\sum\limits_{i=1}^m sz_i-1=n-m$，$m$ 为环的个数。
P2127 序列排序 加权的给置换排序的模型，对一个环拆成自环的时候，考虑两种决策：
- 把全局最小先加入这个环中，然后把其它数给拿出去；
- 直接用环中的最小数把其它数拿出去。
考虑环与环之间的决策互不影响，所以两种决策取最优即可。
中位数
山区建小学模型
$\sum\limits_{i=1}^n|x-p_i|$ 或 $\sum\limits_{i=1}^n|p_x-p_i|$ 的一般最值问题。取其中位数，可能会用不同的算法维护。
一座桥就是朴素的山区建小学问题，把 $s$ 和 $t$ 都扔到数轴上取中位数算即可。
考虑如果有两座桥。每一个人有两个决策，选 $A$ 桥还是选 $B$ 桥。以桥为分界划分为三部分：
考虑如果某个人的起点在 $I$ 区或 $III$ 区，那么对于这个人，一定可以选靠近这个人起点 的桥，因为远离的桥不优。那么只需考虑如果一个人的起点和终点都在 $II$ 区的情况。
设两座桥的位置为 $x,y$ 且 $x<y$，起点的位置为 $s$，终点的位置为 $t$。
那么走 $A$ 桥优于 $B$ 桥，当且仅当：
$(s-x)+(t-x)<(y-s)+(y-t)$
$\Rightarrow s+t<x+y$
也就是对于所有 $s+t<x+y$ 的人，都走 $A$ 桥，反之都走 $B$ 桥。也就是我们去枚举所有的断点 $s+t$，这样两边就是 $k=1$ 的朴素山区建小学，我们动态维护两边的中位数，时间复杂度为 $\mathcal{O}(n\log n)$。
（思考）在推出 $s+t<x+y$，一直陷入一个误区：当我们枚举 $s+t$ 也就确定了 $x+y$，但可能两边所划分的中位数，也就是两座桥的具体位置不能为 $x+y$ 该如何解决？
（解答）经过教练的指导，发现这个式子的意义是，我们找到了一种排序方式（按 $s+t$ 排序）使得对于小于 $x+y$ 的 $A$ 桥，大于 $x+y$ 的一定走 $B$ 桥，那么我们不再关心桥的具体位置，而是最优解的形式一定为以 $s+t$ 排序的前缀走 $A$ 桥，$s+t$ 的后缀走 $B$ 桥，这样两边山区建小学一定不会丢失最优解。
（思想）对于一个要求较强的结论，考虑退而求其次是否更容易地使用。
贪心
冰红茶模型/排队模型
在一个集合中进行若干次决策，对于每一次决策所选中的点，又会补充一个劣于当前解的后继（重点），这样每次必然是选择最优解，然后更新新后继，用优先队列维护。
U130967 冰红茶(tea) 冰红茶模型模板题。
考虑对第 $i$ 站使用加速器，影响了一段从第 $i$ 站开始，到之后的一站之间下车的人，记为 $p_i$。
如果使用加速器，一定会导致 $p_i$ 减小（到达 $p_i$ 站的时间更短），所以下次再选 $i$ 时答案变劣，所以冰红茶即可。
本题仍有用线段树优化贪心使复杂度变为 $\mathcal{O}(n\log n)$ 的做法，具体可见代码。
P5283 [十二省联考 2019] 异或粽子 $n$ 个班排队模型的例题，省选也是有考这些基础算法的题的。
相邻交换法
相邻交换 yyds
使用相邻交换法的前提是推一个具有传递性 $(a<b,b<c\Rightarrow a<c)$ 的比较关系，排好序后即能轻易的得出一系列最优决策。
拆 $\max,\min$ 法
$a>\max(b,c)\Leftrightarrow a>b\text{ and }a>c$
$\max(b,c)>a\Leftrightarrow b>a\text{ or } c>a$
$a>\min(b,c)\Leftrightarrow a>b\text{ or }a>c$
$min(b,c)>a\Leftrightarrow b>a\text{ and }c>a$
设前缀积 $mu_i=\prod\limits_{j=1}^i a_i$，那么每个人的金币数为 $\lfloor\dfrac{mu_{i-1}}{b_i}\rfloor$。
我们取出一个二元组 $(i,j)$，其中 $i<j$，本题中并不能得出越靠后的大臣获得的金币越多的结论。
我们设 $1\sim i-1$ 大臣左手的数的积为 $mu_1$，$i+1\sim j-1$ 大臣左手的数的积为 $mu_2$。
在 $i,j$ 交换前，$i$ 获得的金币数 $\lfloor\dfrac{mu_1}{b_i}\rfloor$，$j$ 获得的金币数 $\lfloor\dfrac{mu_1\cdot a_i\cdot mu_2}{b_j}\rfloor$。
在 $i,j$ 交换后，$i$ 获得的金币数 $\lfloor\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}\rfloor$，$j$ 获得的金币数 $\lfloor\dfrac{mu_1}{b_j}\rfloor$。
相邻交换法的常见套路，不妨设交换前的答案优于交换后的答案。
则有 $\max(\lfloor\dfrac{mu_1}{b_i}\rfloor, \lfloor\dfrac{mu_1\cdot a_i\cdot mu_2}{b_j}\rfloor)<\max(\lfloor\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}\rfloor, \lfloor\dfrac{mu_1}{b_j}\rfloor)$。
其中下取整不影响答案，去掉后变为 $\max(\dfrac{mu_1}{b_i}, \dfrac{mu_1\cdot a_i\cdot mu_2}{b_j})<\max(\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}, \dfrac{mu_1}{b_j})$。
用拆 $\max$ 法，$\Leftrightarrow \max(\dfrac{mu_1}{b_i}, \dfrac{mu_1\cdot a_i\cdot mu_2}{b_j})<\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}\text{ or }\max(\dfrac{mu_1}{b_i}, \dfrac{mu_1\cdot a_i\cdot mu_2}{b_j})<\dfrac{mu_1}{b_j}$
$\Leftrightarrow (①\dfrac{mu_1}{b_i}<\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}\text{ and }②\dfrac{mu_1\cdot a_i\cdot mu_2}{b_j}<\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i})\text{ or }(③\dfrac{mu_1}{b_i}<\dfrac{mu_1}{b_j}\text{ and }④\dfrac{mu_1\cdot a_i\cdot mu_2}{b_j}<\dfrac{mu_1}{b_j})$
现在我们就把 $\max$ 拆成了两两的元素比较和逻辑运算，接下来我们来看看有没有显然成立或不成立的逻辑式。
不难发现，①式显然成立，④式显然不成立，这样我们神奇的发现：
$\Leftrightarrow ②\dfrac{mu_1\cdot a_i\cdot mu_2}{b_j}<\dfrac{mu_1\cdot a_j\cdot mu_2}{b_i}$
$\Leftrightarrow a_i\cdot b_i<a_j\cdot b_j$
没错，我们的得到了一个简单的式子，并且此式满足传递性，于是排序后得到的即为我们所求的最优解。
国王游戏的加强版，一个更难推的相邻交换。
本题可以得出越靠后的大臣奖金越多的结论。
这次我们用相邻两个人 $(i,j)$ 比较，其中 $j=i+1$，设 $\sum\limits_{i=1}^{i-1} a_i$ 为 $s$，那么在交换前 $c_j>c_i$，$c_i=\max(c_{i-1},s+a_i)+b_i$，$c_j=\max(\max(c_{i-1},s+a_i)+b_i,s+a_i+a_j)+b_j$ ，交换后 $c_j<c_i$，$c_j=\max(c_{i-1},s+a_j)+b_j$，$c_i=\max(\max(c_{i-1},s+a_j)+b_j,s+a_j+a_i)+b_i$。
不妨设交换前的答案不劣于交换后的答案，则有：
$\max(\max(c_{i-1},s+a_i)+b_i,s+a_i+a_j)+b_j\le\max(\max(c_{i-1},s+a_j)+b_j,s+a_j+a_i)+b_i$
$\Leftrightarrow \max(\max(c_{i-1},s+a_i)+b_i+b_j,s+a_i+a_j+b_j)\le\max(\max(c_{i-1},s+a_j)+b_j+b_i,s+a_j+a_i+b_i)$
$\Leftrightarrow \max(c_{i-1}+b_i+b_j,s+a_i+b_i+b_j,s+a_i+a_j+b_j)\le\max(c_{i-1}+b_i+b_j,s+a_j+b_i+b_j,s+a_i+a_j+b_i)$
两边的 $\max$ 中各有三个元素，拆起来麻烦怎么办？
考虑两边有相同的元素 $c_{i-1}+b_i+b_j$，那么证明一个结论：$\max(a,b)\le\max(a,c)\Rightarrow b\le c$。
- 如果 $b\le c$，则已经满足条件；
- 如果 $b>c$，那么 $b\le a$，交换后同样满足。
综上可知结论成立。那么进行一步简化：
$\Rightarrow \max(s+a_i+b_i+b_j,s+a_i+a_j+b_j)\le\max(s+a_j+b_i+b_j,s+a_i+a_j+b_i)$
然后就可以进行愉快的拆 $\max$ 环节了！
$\Leftrightarrow \max(s+a_i+b_i+b_j,s+a_i+a_j+b_j)\le s+a_j+b_i+b_j\text{ or }\max(s+a_i+b_i+b_j,s+a_i+a_j+b_j)\le s+a_i+a_j+b_i$
$\Leftrightarrow (s+a_i+b_i+b_j\le s+a_j+b_i+b_j\text{ and }s+a_i+a_j+b_j\le s+a_j+b_i+b_j)\text{ or }(s+a_i+b_i+b_j\le s+a_i+a_j+b_i\text{ and }s+a_i+a_j+b_j\le s+a_i+a_j+b_i)$
$\Leftrightarrow (a_i\le a_j\text{ and }a_i\le b_i)\text{ or }(b_j\le a_j\text{ and }b_j\le b_i)$
上述条件并不满足传递性，所以我们尝试转化排序方式，使得 $\forall i,j\in [1,n],i<j$，都能满足上述条件。
观察到 $\text{or}$ 的两边都有一个 $a$ 和 $b$ 一起的比较，那么我们尝试先按此分组。
如果 $a_i<b_i$，分到 $1$ 组；
如果 $a_i=b_i$，分到 $2$ 组；
如果 $a_i>b_i$，分到 $3$ 组。
在 $1$ 组中的数，可以同时再去满足 $a_i<a_j$，按 $a$ 升序排序，在 $2$ 组中的数，不满足上述条件，可以随意排序，在 $3$ 组中的数，可以同时再去满足 $b_j<b_i$，按 $b$ 降序排序。
那么关键的问题是组与组之间的排序。这里给出排序方式：按 $1,2,3$ 组排序即可。
证明一下：如果想要证明上述排序方法成立，只需保证按此方法排序后 $\forall i,j\in [1,n],i<j$，都能满足上述条件，由于组内已经满足，只需考虑组间。
考虑 $1$ 组和 $2$ 组，则有，$a_i\le b_i,a_j=b_j$。假设可以交换，即不满足上述条件。若不满足条件，则 $a_i\le a_j$ 不能成立，即 $a_i>a_j$，$b_j\le b_i$ 也不能成立，即 $b_j> b_i$，整理条件可得矛盾。
其它情况同理，最终可以保证排序的正确性。
贪心反悔
一大常用的贪心套路。大体流程是优先满足时间较早的决策，在不能满足当前决策的情况下，在已选的决策集合中找到最不优的，然后替换。在正确性下，我们保证：每一次反悔操作不会使答案变劣。
解决的题目一般满足如下性质：
- 题目有最优子结构性质（即无后效性）
- 容易维护决策的集合的性质（即可以方便的反悔）
P2209 [USACO13OPEN]Fuel Economy S
经典反悔贪心，因为每个加油站都可加无限多的油，想象油箱中每种价格的油是分层的，那么在到达每一个加油站的时候，用此加油站的油替换掉所有在油箱中价钱高于当前加油站价格的油，并把油箱加满，此过程即为反悔。在行走的过程中，优先消耗便宜的油，这样我们就维护了整个过程，到达终点后要把多的油退掉。
时间复杂度为 $\mathcal{O}(n\log n)$。
本题还有一个加强版，请见CF1238G，此题中每一站的供应存在限制。
对于一个股票，在买入的时候我们可以看作无代价买入，只有卖出的时候才获得收益。
例如我们已经购入了价格为 $x$ 的股票，现在以 $y$ 的价格卖出，此时我们的收益获得了 $y-x$。
考虑我们如何进行反悔操作。对于价格为 $x$ 的股票，我们要将 $y$ 的价格卖出修改为以 $z$ 的价格卖出，即收益从 $y-x$ 变为 $z-x$，变化了 $z-y$。基于此，我们维护一个小根堆，对于当天的价格 $p$，我们首先将 $p$ 插入，代表原物品，如果 $p$ 还能大于堆中的最小值的话，那么我们就可以先获得 $p-q.top()$ 的代价，然后再次插入 $p$ 这个价格，代表可用作被反悔的物品，这样每次的购买就既有可能是对于原价买入物品的卖出，也有可能是已经被卖出物品的反悔操作。
一个问题：插入两次物品会不会出现不合法的情况，能不能只插入一次。
插入两次同一个物品的目标无非就是两个物品都有可能会用到，我们不妨分析两个物品都用到的情况。
对于一个股票在 $p_i$ 买入，在 $p_j$ 卖出，那么此时堆里存有两个 $p_j$，分别代表 “在 $p_i$ 买入，在 $p_j$ 卖出的决策”和“我有一个价值为 $p_j$ 的股票已经买入”，那么如果在 $p_k$ 的时候堆顶为 $p_j$（如果堆顶被弹出，下一个堆顶也是 $p_j$），我们首先拿出”在 $p_i$ 买入，在 $p_j$ 卖出的决策”，改为”在 $p_i$ 买入，在 $p_k$ 卖出的决策”，经此修改后，$p_j$ 就成为了一个既没有买也没有卖的元素，那么在下一次 $p_l$ 取出 $p_j$ 的时候，即为”在 $p_j$ 买入，在 $p_l$ 卖出的决策”，这样插入两次物品不仅能够保证合法，还是保留最优解的充分条件。
超级钢琴模型
超级钢琴其实类似冰红茶，最基础的情况，两两点之间有一个代价，求代价的最大值。一个点 $i$ 我们对应若干个决策区间，先预处理出区间中的与 $i$ 所得代价的最大值并记录位置 $p$，那么在选择这个之后，将当前的决策区间 $[l,r]$ 拆成 $[l,p-1]$ 与 $[p+1,r]$，因为 $p$ 是 $[l,r]$ 中的最大值，所以分成 $[l,p-1]$ 和 $[p+1,r]$ 后的答案一定要劣于 $p$，这就是一个冰红茶的过程。
此类题所有的特定条件：
- 求一定点所构成的代价的最值
- 容易维护决策区间的最大值
超级钢琴模型的运用灵活，作者见过的题不多，希望以后遇到后还能认真总结。
时光倒流
时光倒流其实是一类经典的思想，具体是如果按正向时间不好维护决策的时候，看看倒序解决能不能有事半功倍的效果。
例如正序的删点维护连通性，我们可以改为倒序加点，这样就可以轻易的维护。
在贪心上，时光倒流有时也可以起到奇效。
适用的题为正序没有最优子结构性质但倒序有最优子结构性质的题目。
考虑按时间正序做需要维护删除操作，但显然删除并不好维护，那么考虑时光倒流变成加点，再将第二类限制反过来，用拓扑随便贪心做一下即可，复杂度 $\mathcal{O}(nm)$。
正序我们同样需要维护讨厌的删除操作，如果改为倒序，“每天少 $x_i$ 单位蔬菜”就变成了“蔬菜从 $app_i$ 天开始每天多 $x_i$ 单位蔬菜”，然后我们就可以在每天贪心的取最大的 $m$ 个。
考虑现在求的答案是所有天数的答案，即 $ans_{100000}$，那么如何求其它天数 $1\sim 99999$。
不难发现，选择了售卖的菜之后，我可以随意的安排这些菜的售卖顺序，因为越往后菜越多，所以在前面的天数这些菜并不会消失，所以从第 $j$ 天推到第 $j-1$ 天时我们只要去掉最便宜的 $m$ 个菜就行。
注意可能在倒序做的时候有的天数可能卖不到 $m$ 个菜，但正序的时候由于这些售卖操作都可以理解为在前 $j$ 天的紧凑操作（即每天卖菜数不存在浪费），所以当且仅当 $m\times j$ 小于现在卖过的菜的总量，我们才需要去删除多余的菜。
双序列匹配
给两个序列 $a$ 和 $b$，在改变 $a,b$ 的顺序后使得一个计算代价的函数 $f(a,b)$ 得到最值，这种一般可以用贪心的匹配得到答案。
给定序列 $a,b$，任意改变 $a,b$ 的顺序，求 $\sum(a_i-b_i)^2$ 的最小值。
最基础的双序列匹配问题，不考虑交换次数的话，将 $a,b$ 都按升序排列得到的即为最小值。交换次数最小我们只需将 $b$ 数组映射到 $a$ 数组，然后求逆序对即可。
这应该算是一个贪心双序列匹配的经典好题了，首先我们不妨二分出一个时间，代表花费的最长时间，那么我们首先可以将所有军队向上跳，显然如果军队能向上跳，那么向上跳肯定不劣。
在所有的军队都向上跳完后，有的叶子肯定没有被军队挡住，我们把这些叶子对应的根的儿子的子树标记，代表这个子树需要被帮助，找到了所有需要帮助的子树后，我们要去用已经到达根的儿子的点的一些军队且还有空余时间走到其它的树来帮助别的子树。（注意当这个在根的儿子的军队去帮助别的子树的时候，它自己这棵子树可能就有拦不住疫情了）
考虑如果一个在根的儿子的军队走到根了之后却不能原路返回再走回自己，且当这个军队走了之后这个子树会失控，那么这个军队应不应该去帮助别人？
如果这个子树帮助别人，那么一定还需要另一个子树上的军队来帮助它，那么我们不如让这个子树的军队不动，这样我们用了更小代价去防控了一个更难防控的子树，这样会更优一些。
最后我们就找到了所有能动的军队和需要被帮助的子树，把距离处理出来，然后双序列贪心匹配，看能不能将帮助所有子树。
时间复杂度 $\mathcal{O}(n\log n\log w)$。
动态规划
同样是极其重要的一类问题，整理基本模型，拓展模型和有意思的想法。
背包
背包的形式也很多样，记几个不常见的类型。
删除背包
删除背包当且仅当仅当背包的运算方式可逆时能用，例如加减可逆，但取 $\max$ 和 $\text{or}$ 都不行。
例如我们要01背包求方案数，每来一个物品，转移如下：
for(int i = M;i >= w;i--) {
dp[i] += dp[i - w];
}
那么如果要删除一个物品，其实也很简单：
for(int i = w;i <= M;i++) {
dp[i] -= dp[i - w];
}
可行性背包可以通过转化成求方案数使用删除背包。U76029 货币系统
$\text{bitset}$ 优化可行性背包
只是一个小优化，但只能用来优化可行性背包。在这里记录一下用法：
- 定义一个大小为 $N$ 的 $\text{bitset}$
bitset<N> f;
- 访问 $\text{bitset}$ 的第 $i$ 位
f[i]
- 查询 $\text{bitset}$ 中 $1$ 的数量
f.count()
- 将所有位设为 $0$
f.reset()
- 可行性背包中新来一个物品后
f = f | (f << w)
其它操作见 bitset - OI Wiki，使用 $bitset$ 后会使原复杂度乘上一个 $\dfrac{1}{w}$ 的常数，$w$ 为计算机的位数32/64。
P6567 [NOI Online #3 入门组] 买表 注意此题的正解是单调队列优化多重背包，但由于是可行性背包，二进制分组加 $\text{bitset}$ 优化可以吊打单调队列。
P5289 [十二省联考 2019] 皮配
一道复杂背包的问题。
我认为背包唯一要讲的就是皮配，讲了这题你其它背包就都会了。——教练
作为一道省选题，我们以考场视角来思考这道题目。在读了一会儿题面后，我们总结出了如下的形式化题面：
一共有 $n$ 个物品， $c$ 种类别，每个物品还有一个重量。
现在你将 $n$ 个物品放置在一个 $2\times 2$ 的网格中，要求：
- 第 $1$ 行重量和 $\le C_0$，第 $2$ 行重量和 $\le C_1$，第 $1$ 列重量和 $\le D_0$，第 $2$ 列重量和 $\le D_1$；
- 同类的物品只能在同一行中放置；
- 每个物品还有一个限制，代表 $4$ 个格子中有一个不能放，或者无限制。
现在求 $n$ 个物品全部放入 $2\times 2$ 的不同方案数，对 $998244353$ 取模。
你的第一天已经有了很稳的分数，所以第二天继续求稳，我们当然是从暴力分想起。
先来看朴素暴力：对于每一类物品，将其视作一个阶段，我们解决当前阶段的问题。
设 $dp_{i,j}$ 表示在当前这一类做之前，第 $1$ 行的总重量为 $i$，第 $2$ 行的总重量为 $j$ 的方案数。第 $2$ 行和第 $2$ 列当前重量可以减一下得到。
对于当前城市的贡献，记一个 $f0_j,f1_j$ 表示都放入第 $1$ 行，第 $1$ 列重量为 $j$ 的方案数和都放入第 $2$ 行，第 $1$ 列重量为 $j$ 的方案数。
那么我们直接看每个物品取哪个位置，然后更新 $f_0,f_1$。最后更新即为：
$dp_{i,j}+f0_k\rightarrow dp_{i+k,j+k},dp_{i,j}+f1_k\rightarrow dp_{i,j+k}$。
计算 $f$ 的总复杂度为 $\mathcal{O}(nM)$，$f$ 合并到 $dp$ 的总复杂度为 $\mathcal{O}(nM^3)$，得分 $40$。
这是一个好想加好写的做法，你不难推测大部分人都会这个做法，让我们向着更高的目标前进！
接下来我们考虑一个优化：平衡转移和合并的复杂度。
我们能否将合并的复杂度分一个 $M$ 给转移，使其平衡至 $\mathcal{O}(nM^2)$。
不难发现可行，给 $f0$ 和 $f1$ 加上一维，表示此类物品加上之前类的第 $1$ 行已有的重量，原先的一维也变为了此类物品加上之前类的第 $1$ 列已有的重量。
在转移每一类物品前，复制 $dp$ 至 $f0,f1$，决策这一类的所有物品后，将 $f0_{i,j}+f1_{i,j}$ 更新至 $dp_{i,j}$，由于当前类的物品在第 $1$ 行还是第 $2$ 行是两种选择，可使用加法原理。
现在你获得了 $50$ 分，于是你开始决定拼特殊情况。
当 $k=0$，即没有带限制的物品该怎么做？
你发现此时决策物品的行与列不会再受到限制，行列可看作互相独立的问题，那么我们记 $g_i$ 表示第 $1$ 行重量为 $i$ 的方案数，$h_j$ 表示第 $1$ 列重量为 $j$ 的方案数，把每一类的重量绑在一起做行，每个单独的物品做列，最后行列使用乘法原理乘起来即可。
$\sum\limits_{i,j}[i\le C_0][W-i\le C_1][j\le D_0][W-j\le D_1]g_i\cdot h_j$
$W$ 表示所有物品的总重量。
这个做法是 $\mathcal{O}(nM)$ 的，加上之前的做法有了 $70$ 分。如果你受到了这个行列独立的启发后，不妨再思考一下。
注意下列的状态全部重新命名，可能和上面有重合。
将 $n$ 个物品分为 $3$ 种类型：
- $\text{A}$ 类：所在类的所有物品全部无限制。
- $\text{B}$ 类：自己无限制，但所在类有物品有限制。
- $\text{C}$ 类：自己有限制。
分成这 $3$ 类后，我们先考虑 $\text{A}$ 类。$\text{A}$ 直接用 $k=0$ 的转移就行了，我们存入 $f_i$ 与 $g_j$ 中。时间复杂度 $\mathcal{O}(nM)$
接下来我们考虑 $\text{B}$ 类，$\text{B}$ 可以理解为行的选择存在一定限制，但列还是完全没有限制，因为它在它自己的类中决策了行之后，它自身是可以随便选第 $1$ 列和第 $2$ 列的，于是我们把列的信息一块记到 $g$ 中代表了列的决策独立，而对于行的信息，其实就是在转移 $\text{C}$ 类点后增加了这一类中 $\text{B}$ 类点的总重量，那我们设 $h_{i,j}$ 表示 $\text{B}$ 的行与 $\text{C}$ 的行和列的第 $1$ 行重量为 $i$，只算 $C$ 的重量时第 $1$ 列重量为 $j$ 的方案数，做 $\text{C}$ 的时候按上面的 $\mathcal{O}(nM^2)$ 转移，最后加上一个当前类的 $\text{B}$ 的总重量决策是第 $1$ 行还是第 $2$ 行即可。
$\text{C}$ 存在限制，但 $k\le30$，即我们使用暴力的转移复杂度实际上是 $\mathcal{O}(kM^2)$ 的，但你发现 $s_i\le 10$，即任意物品的重量不超过 $10$，那么 $h$ 的第二维大小只有 $30\times10=300$，复杂度可再次降至 $\mathcal{O}(300M)$，可以接受。
这样我们对于每类点的行列信息都存在了如下的数组中：
| 行 | 列 | |
|---|---|---|
| $\text{A}$ | $f$ | $g$ |
| $\text{B}$ | $h$ | $g$ |
| $\text{C}$ | $h$ | $h$ |
最后，如何计算出总方案数？
我们考虑 $f,g,h$ 是不是互相独立的，我们首先用 $h$ 确定了 $\text{C}$ 的行列和 $\text{B}$ 的行信息，此时我们对 $\text{B}$ 的列和 $\text{A}$ 的行列的选择并没有产生影响，然后用 $f$ 确定了 $\text{A}$ 的行信息，由于 $\text{A,B}$ 点一定不是在同一类中（$\text{A}$ 的定义：所在类的所有物品全部无限制），那么我们对 $\text{A,B}$ 的列也没有产生影响，也就是 $g$ 的方案数。由此可见 $f,g,h$ 各自的选择都不会影响到其它的选择，所以我们枚举 $f,g,h$ 所有可能状态，运用乘法原理求出每一种组合的答案，在实现上，对 $f,g$ 做前缀和，然后枚举 $h$ 的状态，$f,g$ 的选取是一个区间，这样复杂度是 $\mathcal{O}(300M)$ 的。这样我们就愉快地通过了这道题。
最后，我们可以总结一下这道题所用到的一些 dp 思想：
- 对于状态的设计：对于每一类物品，将其视作一个阶段，解决完当前阶段合并至之前的答案形成新的答案继续转移，无论是暴力还是正解都没有脱离这个前提。
- 转移与合并的平衡：在转移和合并复杂度差距较大时，观察到其中的特点，例如此题在转移的时加了一维状态来辅助合并，优化了整体复杂度。
- 若干独立情况的整合：我认为这是本道题的精华所在。在做 $k=0$ 的时候就已经有行列独立的美妙性质，正解对若干个情况独立的分别解决的思路也是登峰造极。这题的数据范围对于这种想法也有提示，如 $k\le30,s_i\le10$，观察到这些是否可以想到有限制的物品和无限制的物品分开做呢？
计数 dp
容斥
考虑如果没有主要食材在一半的菜的条件求方案，用乘法原理求求方案。
那么如何求出不合法的方案数？考虑到最多只有一种主要食材会超过一半，那么我们枚举哪个食材超了，然后 $dp_{i,j}$ 表示前 $i$ 行，钦定的食材数量的选择数比其它选择的食材数量多 $j$ 的方案数。
转移就是当前这行不选/选钦定食材/选其它食材三种转移，然后 $j\in [-n,n]$，答案的取值范为 $dp_{n,j},j\in[1,n]$，当然要先平移一下内存存储。
时间复杂度 $\mathcal{O}(mn^2)$。
优化思想：
合法方案不方便求，但是总方案非常好求，而不合法方案在本题的限制下也变得非常好求，所以采用了容斥的思想。
双调巡游
双调巡游，即为求出选择 $2$ 条方向单调且点互不相交路径的一类问题。
如：给定一个 $n$ 个点 $m$ 条边的带边权有向图，问选择两条点不相交的最短路径的方案数是多少。
首先把最短路 DAG 求出来，那么路径方向就是单调的，可以使用双调巡游。
如果我们按 $1\rightarrow u$ 的路径长度大小给所有点重新标号，那么每拓展一次最短路编号一定越来越大。
设 $dp_{x,y}$ 表示一条路径走到了 $x$，另一条路径走到了 $y$ 的方案数，初值 $dp_{1,1}=1$，最终答案为 $dp_{n,n}$。
对于 $dp_{x,y}$ ，其中 $dis_x\le dis_y$，那么我们去转移所有 $x$ 在最短路上的出边更新状态即可，复杂度 $\mathcal{O}(nm)$。
树
一些基本的树概念就不写了。
树的直径 $\text{(diameter)}$
形式化的定义树的直径，对于直径 $(x,y)$，$\forall (u,v),dist(u,v)\le dist(x,y)$，也就是直径是树上任意两点最长距离的点对。
树的直径的求法一般为两遍 dfs，或者树形 dp，复杂度 $\mathcal{O}(n)$。
直径常规套路为把直径拉起来，子树挂在直径的链上，进行一系列相关操作。
P2491 [SDOI2011] 消防 把直径拉出来后，首先可以证明选的路径一定在直径上，那么选择的部分就是一个滑动窗口，拿单调队列去优化，当然这题用带 log 的倍增也行，复杂度 $\mathcal{O}(n\log n)/\mathcal{O}(n)$。
同样是将直径拉出来，首先可以明确一点，如果不修改直径，直径不会变小，但是如果根本就不修改，直径一定不変。那么每次修改仅有可能在直径上修改。也就是我们在看直径上的所有边被修改后，直径会不会变小，不会取原直径即可。那么现在有一个 $\mathcal{O}(qn^2)$ 的暴力做法：每次询问枚举哪条边修改，然后暴力计算修改后的直径。
考虑优化，记录 $dist$ 为直径长度，$dep_u$ 表示以直径上的点 $u$ 为根的子树到子树内最深点的距离，$pre_u$ 表示直径上 $u$ 节点到 $u$ 之前所有位置的最长距离，$suf_u$ 表示直径上 $u$ 节点到 $u$ 之后所有位置的最长距离，$pre_u$ 和 $suf_u$ 可以通过递推求出。
假设我们要修改直径上的一条边 $(u,v)$，从 $w0$ 改成 $w$，那么新的直径一定是：
$\max(pre_u, suf_v, dist-w0+w)$
观察这个式子，除了 $dist-w0+w$ 这一项随着询问不同的权值改变，而前两项只跟这条边的位置有关。那么设 $Val_u=max(pre_u, suf_v)$，那么当 $Val_u\ge dist-w0+w$ 时，取前者，否则取后者。整理可得 $w\le Val_u-dist+w0$，那么我们以 $Val_u-dist+w0$ 升序排序，那么满足一段前缀，取得的最大值为 $Val_u$，后缀的最大值为 $dist-0+w$，二分查一下再次维护一个前后缀答案的 $\max$ 即能通过。复杂度 $\mathcal{O }(n\log n)$。
最近公共祖先 $\text{(Lowest Common Ancestor)}$
树的重要知识，很多题都需要求 lca 辅助做题。
lca 的求法一般掌握两种求法即可，一个是在线倍增做法 $\mathcal{O}(n\log n)-\mathcal{O}(\log n)$，一个是离线 tarjan 做法 $\mathcal{O}(n\alpha)-\mathcal{O}(1)$。不会有人想学 $\mathcal{O}(n)-\mathcal{O}(1)$ 的 $\text{Method of Four Russians}$ 吧。
lca 相关性质：
- $\text{LCA}(u)=u$
- $u$ 是 $v$ 的祖先，当且仅当 $\text{LCA}(u,v)=u$
- 前序遍历（根左右）中，$\text{LCA}(S)$ 出现在 $S$ 点集所有点之前；后序遍历（左右根）中，$\text{LCA}(S)$ 出现在 $S$ 点集所有点之后。
- 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 $\text{LCA}(A,B)=\text{LCA(LCA(A), LCA(B))}$。
- $dist(u,v)=dep_u+dep_v-2dep_{lca}$。
- $\text{LCA}(l\sim r)=\text{LCA}(x,y)$，$x$ 和 $y$ 分别是 $l\sim r$ 中 dfn 序最小和最大的节点。
树上距离问题
- 点 $x$ 到路径 $(u,v)$ 距离：$\dfrac{dist(x,u)+dist(x,v)-dist(u,v)}{2}$
- 点 $x$ 是否在路径 $(u,v)$ 上，利用上式判是否等于 $0$。
- 两条直径 $(u_1,v_1)(u_2,v_2)$ 是否点相交：判断 $lca_1$ 和 $lca_2$ 是否分别在路径 $(u_2,v_2)$ 和 $(u_1,v_1)$ 上。
- 两条路径边相交的长度：$\dfrac{|dist(u_1,v_2)+dist(u_2,v_1)-dist(u_1,v_1)-dist(u_2,v_2)|}{2}$，顺便可判边相交。Crabby_Maskiv
- 两条路径之间的距离： $\dfrac{dist(u_1,v_2)+dist(u_2,v_1)-dist(u_1,v_1)-dist(u_2,v_2)}{2}$，若路径点相交为 $0$。
树上差分
树上差分定义：$d_u=a_u-\sum\limits_{v\in son_u}a_v$，最后利用差分求回原值：$a_u=\sum\limits_{v\in tree_u,v\neq u}d_v$。
经典问题
- 子树修改，子树查询：线段树 dfn 序 $\rightarrow$ 区间修改，区间查询。
- 单点修改，路径查询：路径查询转为根到节点的路径长度，那么单点修改就变成了子树查询。
- 路径修改，单点查询：用树状数组实现单点修改/子树查询。
- 路径修改，子树查询：记录 $\sum d_u$ 和 $\sum d_u\times dep_u$ 的权值，开两个树状数组维护。
路径修改，路径查询：树剖。
重心 $\text{(centriod)}$
定义：
- 如果以重心为根，每个子树的大小不超过 $\lfloor \dfrac{n}{2}\rfloor$。
- 树上山区建一所小学应该建在重心。（其它点的距离到重心的距离最短）
- 在一棵树上添加或删除一个叶子，那么重心最多只移动一条边的距离。（同时可以尝试拓展到添删一棵子树）
- 以 $u$ 为根的子树的重心必定在以 $u$ 为 $top$ 的重链上。