题解：P17859 白露 / ros

xxxxxzy · 2026-11-08 18:20:03 · 题解

似乎有更简单的做法？

考虑如何设计状态去做 dp。尝试插入一个 a_{i+1}，观察一下。记 a_{1 \sim i} 的最大值为 \max，次大值为 \sec。

• 如果 a_{i+1} \ge \max：那么 a_{i+1} 不会受到任何约束。
• 如果 a_{i+1} < \max，那么 a_{i+1} 一定会和 \max 在树上相邻，否则不合法。但是这并不充分，思考一下，我们发现 a_{i+1} 还会收到除了 \max 其他数的约束，我们先考虑 \sec 的约束。
  • 如果 \sec \le a_{i+1} < \max，则 a_{i+1} 不会被 \sec 约束。
  • 否则，则 a_{i+1} 必须位于 \sec 的邻域里。

由于树上两个不同点 \max 和 \sec 邻域的交最多只有一个点，而第三大值及其更小的值只会对这个点约束，所以我们考虑设计 dp：设 f_{i,j,k,0/1} 代表考虑序列 a_{1 \sim i}，当前 \max = j，\sec = k，是否存在一个点，使得可以在 i+1 被选。很显然，这个点如果存在，一定是 \max 和 \sec 的邻域的交点。记 e_{u,v} 代表 (u,v) 间是否有边，考虑转移：

前面的转移应该都是平凡的，接下来考虑最大值改变的情况。记改变后的最大值为 j'，讨论：

• 如果 G_{j'} \cap G_j = \varnothing：直接转移 (f_{i,j,k,0}+f_{i,j,k,1}) \to f_{i+1,j',j,0}。
• 否则，记 G_{j'} \cap G_j = u', G_{j} \cap G_k =u ：
  • 对于 f_{i,j,k,0} 的转移，特殊点 u' 存在的条件是必须要有 k \le u' < j，所以转移为 f_{i,j,k,0} \to f_{i+1,j',j,[k \le u' < j]}。
  • 对于 f_{i,j,k,1} 的转移，特殊点 u' 除了上述条件，若 u'=u，也可以直接转移。所以转移为 f_{i,j,k,1} \to f_{i+1,j',j,[k \le u' < j] \vee [u=u']}。

观察一下，状态数是 O(mn^2) 的，而转移是 O(n) 的，这样我们就得到了一个 O(mn^3) 的做法。

考虑如何优化，首先从优化转移下手。转移 O(n) 的地方第一个在于改变次大值的邻域枚举，这个很容易前缀和优化掉；第二个地方在于改变最大值的时候需要枚举一个 j'。

考虑什么时候会取到 G_{j'} \cap G_j = u'，这其实就是 j 的一圈二阶邻域会存在这个情况，而跟 k 无关。第一个大类的转移可以直接前缀和优化；对第二个大类的第一种情况，我们枚举 j,j'，对原数组前缀和优化；对于第二类情况，由于 u'=u，所以 j' 总枚举量是 O(n) 的，可以随便做，这样就优化到了 O(mn^2)。

考虑接下来如何优化，肯定需要从状态数上面做文章。一个想法是观察到大部分时候我们并不关心 \sec 的值，而是说我们只关心 \sec 在 \max 邻域中的排名。这启发我们，状态可能可以进行合并，写一个最小化 DFA，发现自动机只会建出来 O(n) 个节点。

考虑如何证明这件事情：

• 对于 f_{*,*,*,0}，我们重设计新的状态：f_{i,\max,k,0/1} 代表当前最大值为 \max，当前次大值 \le 最大值邻域的第 k 大值。特殊地，我们需要单独记 \sec=0 的状态。这样的总状态数是 \sum (d_i + 1) \le 2n，这里 d_i 是 i 邻域比 i 编号小的数。
• 对于 f_{*,*,*,1}，我们如果沿用上面的状态会无法转移，但是我们发现，合法的 (\max,u) 的对数是 O(n) 的，而我们又发现，对于一对 (\max,u)，合法的 \sec 会被划分成 \min(d_{1,\max},d_{2,u})+1 个等价类，这里 d_{1/2,u} 代表 u 周围编号比 u 小的 / 大的数。放缩一下，\sum \min(d_{1,\max},d_{2,u})+1 \le \sum d_{u}+1 \le 2n。

所以我们证明了确实只会有 O(n) 个状态。考虑直接用优化后的状态去做 dp，可以通过一些优化手法做到 O(n \log n + nm)。