令 $a_i=\prod_{j=1}^iA_j$，那么条件转化为
朴素的想法是对 $[0,m)\backslash B$ 中所有满足 $\gcd(x,m)\mid y$ 的 $x$ 向 $y$ 连边，那么图上的最长链长度即为答案。
但是图上有环，难以处理。不过不难发现 $x,y$ 在同一环中当且仅当 $\gcd(x,m)=\gcd(y,m)$。也就是说如果能取 $x$，那么一定能取 $\gcd(y,m)=x$ 的所有 $y\not\in B$。
所以我们将所有 $x$ 按照 $\gcd(x,m)$ 划分等价类建图，在 DAG 上 DP 即可。
将原图称作 $G$，新图称作 $P$，显然 $G$ 中当 $a,x$ 不连通或 $b,y$ 不连通时，$P$ 中 $(a,b),(x,y)$ 一定不连通。
否则不难发现 $P$ 中 $(a,b),(x,y)$ 连通仅当 $a,x$ 之间和 $b,y$ 之间存在长度相等的路径。
如果 $G$ 中 $a,x$ 和 $b,y$ 所在的连通块中至少一个存在奇环，则两个连通块中各选一个构成 $P$ 中的点，均连通。
否则两个连通块中各自黑白染色，能够构成 $P$ 中两个连通块，其中一个由所有 $a,b$ 颜色相同的 $(a,b)$ 构成，另外一个反之。
至于孤点需要特殊处理，因为“奇偶性相同一定可以构造出长度相同的路径”需要至少有一条边来反复走，这个结论对孤点不适用。
对每个点分别求出到它最近的关键点 $f_u$，和它能到达的最近的关键点 $g_u$。
枚举每个点 $u$，如果 $f_u\not=g_u$，用 $k=\mathrm{dist}(f_u,u)+\mathrm{dist}(u,g_u)$ 更新答案。
枚举每条边 $(u,v,w)$，如果 $f_u\not=g_v$，用 $k=\mathrm{dist}(f_u,u)+w+\mathrm{dist}(v,g_v)$ 更新答案。
不难发现上述每个用以更新答案的值 $k$ 都对应着至少一条合法路径，所以我们只需要证明 $k$ 至少一次取到正确答案。
考察所有起点和终点均为关键点的路径中最短的一条 $p_0,p_1,p_2\cdots,p_{m}$，设其长度即原问题答案为 $t$，那么我们有以下结论：
否则不满足 $f$ 或 $g$ 的定义。
由此结论可以得出，我们的更新方法中 $k$ 取不到正确答案 $t$，当且仅当这条路径上的每个点 $u$ 都有 $f_u=g_u$，每条边 $(u,v,w)$ 都有 $f_u=g_v$。那么
$$\displaylines{f_{p_0}=g_{p_1}=f_{p_1}=g_{p_2}=\cdots=g_{p_{m-1}}=f_{p_m} }$$而我们又显然有 $f_{p_0}=p_0\not=p_m=f_{p_m}$。矛盾，所以我们的更新方法一定能够取到正确答案。
初始将所有点按照 $K_i$ 加入小根堆，此时堆顶一定选择法伤而非物伤。因为堆顶选择物伤势必导致至少一个其它怪物选择法伤，代价一定不少于堆顶直接进行法伤。
所以我们取出堆顶，更新其前驱节点，即以它为后继的节点。如果一个节点被它的所有后继都更新过，并且算下来物伤更优，那么将物伤作为它的花费加入堆。正确性类似，已经被弹出堆的点无法再更新堆内节点，所以堆顶能够贪心地确定它的策略。
从左到右依次考虑所有端点，进行决策。
为了便于处理线段重叠的情况，设 DP 状态 $f_{i,j}$ 为前 $i$ 个端点的所有决策中，覆盖点 $j$ 以左的部分最多有多长。
分类讨论这 $i$ 条线段，是否覆盖到了 $a_i$ 以右的点。
没有覆盖的话，$j=a_i$ 时的答案应该由 $j=a_i-l_i$ 的答案转移而来。
否则我们枚举右端点最靠右的线段 $k$，显然此时 $(k,i]$ 中的线段向右延伸一定不优于全部向左延伸。设 $(k,i)$ 中所有线段向左延伸的左端点为 $t$，那么 $j=a_k+l_k$ 时的答案应当由 $j=t$ 的答案转移而来。
此时我们处理完了 $j$ 恰好落在被覆盖的最靠右的点的情形。那么对此从左向右令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j-1})$，再从右向左地依次令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j+1}-1)$。即可。这样做等效于将 $j$ 处的值改为 $\max(\max_{k\le j}f_{i,k},\max_{k>j}f_{i,k}-k+j)$，如果 $i$ 没有被覆盖，那么会取前者，否则会取后者（因为 $f_{i,j+1}-f_{i,j}\in[0,1]$）。
考虑 Kruskal 算法的过程，每次找到权值最小的两端点不连通的边并加入生成森林。
而我们面对的是一张完全图，所以考虑将所有点权放到 01-Trie 上，如果有两对点 LCA 深度不同，那么 LCA 较深的点对之间的边的权值一定较小。也就是说，Kruskal 过程中，所有边一定是按照两端点在 01-Trie 上对应的节点的 LCA 由深到浅被考虑的。
那么着眼于同一层之内，我们要对于这一层中的每个点 $u$，在以它的两个儿子为根的子树内，分别找到一个节点，使他们异或的结果最小。并且对于不同的 $u$，我们的选择之间是独立的。
那么我们遍历这颗 01-Trie，对于每个左右儿子都有的节点，枚举左儿子，在右儿子中查询与它异或后的最小值。这样一个叶子节点最多被 $O(\log v)$ 个父亲查询，每次查询 $O(\log v)$，总时间复杂度为 $O(n\log^2v)$。
[USACO19JAN] Train Tracking 2 P
同一个位置上的数看似可能被多个 $c$ 所限制，但实际上真正限制它的只有所有涉及到它的 $c$ 中最大的。
那么我们转而考察某个极长的 $c_i$ 相等的区间 $[i,j]$ 会对哪个区间做出什么样的限制。
如果该区间的 $c$ 大于其左侧区间，那么它所限制的区间的左端点为 $i$；否则它所限制区间的左端点为 $i+K-1$，并且该区间一定以 $c$ 开头。特别地，第一个区间的开头为起始位置。
如果该区间的 $c$ 大于其右侧区间，那么它所限制的区间的右端点为 $j+K-1$；否则它所限制区间的右端点为 $j$，并且该区间一定以 $c$ 结尾。特别地，最后一个区间的结尾为终止位置。
接下来需要解决这样的问题：求长度为 $n$，任意长为 $k$ 的区间最小值都为 $c$ 的序列的数量。
不难发现这样的要求等价于，每个值不小于 $c$，并且任意长为 $k$ 的区间中均包含至少一个 $c$。
于是 DP，用前 $n-1$ 个数合法，最后一个数任意填的方案数，减去前 $n-1$ 个数合法，长为 $k$ 的后缀中不出现 $c$ 的方案数即可。
一次冒泡排序后区间内的最大值一定会到区间末尾，所以至少会出现一个分割点。那么每个元素对于答案的贡献就等于这个元素进入递归的层数。
不难发现一个元素不再进入下一层递归，当且仅当这个元素左右两侧均有分割点。所以这个元素进入递归的层数等于左右两侧分割点出现时间的较大值。于是我们转而考察每个分割点出现的时间。
而一个位置出现分割点当且仅当所有所有排序后在它左侧的数都在它左侧。考虑到这个目标达成以前，每一次递归，排序后在分界点左侧，此时却在分界点右侧的所有数，都会恰好想左移动一格。也即该分界点第一次出现的时间，等于排序后在分界点左侧的，最靠右的点到分界点的距离。
定义两个长度相同的串 $a,b$ 是同构的，当且仅当对于任意 $i,j$，$a_i<a_j\iff b_i<b_j$。
求短串在长串中的所有同构匹配。
不难想到使用 KMP。那么我们还需要对于每个前缀在指针跳的时候快速判断两个 border 同时各添加一个数后是否仍然同构。一种想法是使用树状数组查询区间内小于 $k$ 的数的个数，时间复杂度 $O(n\log n)$。
更加聪明的做法是用链表 $O(n)$ 预处理每个位置在以它为结尾的前缀中的前驱和后继的位置，两个同构串后各添加一个数后仍然同构，当且仅当该数大于另一个串中添加数在另一个串中的前驱对应到自己串中的位置上的数，小于另一个串中添加数在另一个串中的后继对应到自己串中的位置上的数。
我们称一星通关的关卡为 A 类，二星通关的关卡为 B 类。
将关卡序列按照 $b_i$ 从小到大排序，显然在最优解中所有 B 类关卡一定排在所有未通关关卡之前。
也即我们选择一个分界点，将分界点之前划为 B 类关卡，分界点之后划为 A 类关卡，接着选择一些 A 类关卡改为不通关，选择一些 B 类关卡划入 A 类关卡。一定存在合适的分界点使得上述方案能够得出最优解。
于是我们对于每个可能的分界点，先计算出目前的总代价，然后衡量将分界点左侧的 B 类关卡降格为 A 类和分界点右侧的 A 类关卡改为不通关能够获得的收益，那么此分界点能够构造出的最小代价为总代价减去所有选择中收益前 $2p+q-w$ 大之和，其中 $p,q$ 分别为分界点左右侧关卡数。
那么我们从左到右枚举分界点，用堆维护所有选择的代价即可。