浅谈保序回归问题及其特殊条件下的更优替代解法

//全文约三千字 阅读时间大概半小时 **一些重要的前置芝士** $ 1 $ .动态规划的维护折线优化 常在问题的朴素 $ \rm dp $ 解法很显然，但其他解法不好想(甚至不存在)的时候使用，多用于二维 $ \rm dp $ 的优化，一般需要状态仅依赖于前一列这一条件。 以[此题](https://www.luogu.com.cn/problem/CF573E)为例，很明显有 $ \rm f(i,j) $ 表示前 $ i $ 个数选择 $ j $ 个数的最大答案这一平方级别的动态规划算法。考虑将其进行一个滚动数组，增量式地维护 $ \rm dp $ 结果。 注意到一个性质，每次新加入一个数必定存在一个分界点，使得分界点之前不使用该数，分界点之后使用该数(此结论存在从题目出发的证明，也可以直接从 $ \rm dp $ 的转移方程导出，这里不详细说明）。 于是我们发现可以用平衡树维护差分数组，每次操作相当于在树内二分出一个 $ \rm k $ ，使 $ \rm v_k \leq val*k $ ，在 $ \rm k $ 与 $ \rm k-1 $ 之间插入一个 $ \rm val*k $ ，随后将大于等于 $ \rm k $ 的所有差分元素加上 $ \rm val $ ，较为简便的实现方法有范浩强 $ \rm treap $ 等。 维护折线法往往可以使用平衡树强行搞过去（甚至不需要注意到一些朴素dp都需要的性质，比如练习题一的选值只可能在已有的值内）。如果注意到这些性质，则有可能会有常数更小实现更简单的线段树解法。 [代码实现](https://www.luogu.com.cn/record/82138712) [练习题一(记住这道题，后面还会出现)](https://www.luogu.com.cn/problem/P4331) [练习题二](https://www.luogu.com.cn/problem/P7294) $ 2 $ .陈丹琦分治/整体二分思想 原论文作者觉得他的主要思想是整体二分，但我觉得更像是对值域的 $ \rm cdq $ 分治，因为根本不存在逐个二分的做法。 保序回归相对并没有涉及太多的整体二分知识，稍有了解即可。 [练习题](https://www.luogu.com.cn/problem/P1527) $ 3 $ .网络流 保序回归通解中很重要的一步就是利用最大权闭合子图模型求出对于一个特殊子问题的解，因此读者需要对网络流有所了解。 $ 4 $ .保序回归问题及一些名词的定义 给定一个序列 $ \rm y $ ，一个加权数组 $ \rm w $ ，一张 $ \rm dag $ 图 $ \rm G=(E,V) $ 表示的偏序关系，以及一个阶 $ p $ ( $ 1 \leq \rm p < \infty $ )。 所谓 $ L_p $ 问题即需要构造一个序列 $ \rm f $ 最小化 $ \rm \sum w_i*|f_i-y_i|^p $ ,且满足 $ \forall (u,v) \in \rm E $ ，有 $ f_u \leq f_v $ 。 对于 $ p = \infty $ 的情况，是将求和改为最大值，本篇文章不做讨论。 考虑若存在所有 $ \rm f $ 数组相等的约束，得到的应取值被称为序列 $ \rm y $ 的 $ L_p $ 均值,求导可得 $ \rm L_1 $ 均值为序列的加权中位数， $ \rm L_2 $ 均值为序列的加权平均数。 **正题：保序回归问题的通用解法** $ 1.L_1 $ 问题的通解 考虑构造原问题的子问题 $ \rm S=(A,B)(A < B) $ ，意为在原问题的基础上附加 $ \forall i,A \leq f_i \leq B $ 的条件。 接下来给出一个很强的引理，对于一子问题 $ \rm S=(A,B) $ ，只要满足任意 $ y_i $ 不在区间 $ \rm (A,B) $ 中，且原序列至少有一组最优解没有元素在区间 $ \rm (A,B) $ 中，便能得到如下结论： 若 $ f_a $ 序列为该子问题的最优解，则必定能找到一个原问题的最优解序列 $ f_b $ ，满足 $ \forall f_{a,i}=A,f_{b,i} \leq A $ ， $ \forall f_{a,i}=B,f_{b,i} \geq B $ 。 这个引理的证明相当繁琐抽象，我会尝试尽可能用简洁的语言描述它。 首先，因为引理的两个条件，我们可以断定所有 $ f_{a,i} $ 要么为A要么为B。 我们将满足 $ f_{a,i}=A $ 的点称为A形点，为B的称作B形点。则命题转化为不存在A形点使 $ f_{b,i}\geq B $ ，不存在B形点使 $ f_{b,i}\leq A $ 。明显，这两类点之间不存在偏序关系，因此只需要证明其中一种不存在，不妨选择后一种进行证明。 考虑 $ \rm U $ 为包含所有上述的不满足要求的点(即第二类，下同)中 $ f_{b,i} $ 最大的点的集合，集合 $ \rm U $ 的 $ L_1 $ 均值为 $ k $ ,且设得出的最大值为 $ h $ 。 $ 1.k \geq B $ 感性理解一下，在维持这个集合中所有偏序关系仍满足的情况下， $ f_{b,i} $ 越靠近 $ k $ ，做出的贡献肯定越少，因此可以直接把所有集合 $ \rm U $ 中的 $ f_b $ 值拉到 $ B $ ，偏序关系显然不受影响，答案不劣。 $ 2.k \leq A $ 如果所有B类点都是一种取值，那么我们可以将这些B类点的 $ f_a $ 值全部移动到A，偏序关系显然不变，答案显然不劣。 如果不是，我们设剩余集的 $ L_1 $ 均值为 $ z $ ，若有 $ z\leq h $ ,则明显可以把所有不符合要求的点的 $ f_a $ 值全部移到A，答案不劣，否则，可以将剩余集的所有 $ f_b $ 调整到 $ h $ ，答案不劣。 我们可以循环使用以上结论进行局部调整，最终推得符合引理要求的两个解。且很明显这可以在有限步内完成。 从理论上讲，以上证明实际并不严谨，因为 $ L_1 $ 均值不是一个确切的值而是一个段，有兴趣的读者可以自行阅读原论文的形式化证明。 有了这么一个引理，我们就可以用整体二分了。具体细节是，每次利用最大权闭合子图模型求出对于原问题的 $ S=(mid,mid+1) $ 子问题的最优解，通过残余网络构造出解，随后分治解决，时间复杂度为 $ O(n^2mlogw) $ (如果使用 $ \rm dinic $ ~~当然你可以用林克卡特树把一个n变成log~~)。 $ 2. $ 对于所有保序回归问题的通解 首先有一个结论，当 $ p \geq 2 $ 时，一个集合的 $ L_p $ 均值唯一，这个可以用导数证，此处不加赘述。 然后再给出一个引理：若找到一个区间 $ (A,B) $ 使得 $ y $ 数组的任意子集的 $ L_p $ 均值都不在这个区间中，则其等价于同样的 $ L_1 $ 问题的 $ S=(A,B) $ 问题。 证明大致是因为有前一条件，所以等价于必定能找到一组解不在给定的区间中。 由于子集的 $ L_p $ 均值是有限的，所以对于 $ mid $ 我们肯定能找到一个 $ \omega $ ，让区间 $ (mid,mid+\omega) $ 满足以上条件。 不妨让 $ \omega \to 0 $ ，于是在以上的最大权闭合子图建模中，一个点选择 $ mid $ 的代价就变为了 $ w_i*|y_i-mid|^p - w_i*|y_i-(mid+\omega)|^p $ 。考虑将所有代价同除一个数，最优解构成不变，考虑同除 $ \omega $ ，将代价变为导数形式即可。 [160行的保序回归通用解法代码 修改一下即可A掉CF1615H](https://www.luogu.com.cn/paste/c9xgxpaf) 一些细节问题： 1.以上给出的是规定 $ f_i $ 为整数的版本。因为当 $ r-l+1 = 2 $ 时二分会处于一个不动点，所以要手动把两个相邻整数作为选择再跑一遍网络流。如果要得出浮点数样式精确答案，改为浮点数上二分即可。 2.如果给出的偏序关系是小于而不是小于等于，可以考虑对dag按照距离分层，把每个 $ y_i $ 减去自身对应层数，即可转换为在同样图上的小于等于问题。 3.虽然说是dag，其实不是dag的图也是能跑的。 **特殊形式保序回归问题的特殊解法** 上文给出了一种对于所有保序回归问题的通用解法，然而对于个别特殊的保序回归问题会有更优解法。试以之前出现过的一题作为例子。 [链接](https://www.luogu.com.cn/problem/P4331) 就笔者所知，这题至少有 $ 3 $ 种解法： 解法一：考虑使用维护折线法优化朴素dp，仔细分析可以发现用优先队列维护所有拐点即可，且 $ f(0) $ 的值明显可以快速求出，因此就有了一种 $ O(n\log n) $ 的优秀且简短的解法。论文作者还提到，这种做法同样适用于给定的 $ dag $ 成一棵树的情况。 解法二：为原论文作者所提出的特殊情况简易解法之一。主体思路是，一段下降序列肯定是选择所有值为其 $ L_1 $ 均值即中位数为最优，于是有了一种类似单调栈的解法，维护一个左偏树队列，每次新加入一个单独点组成的左偏树，随后不断向前检查是否违背了单调性，若是，则将两个左偏树合并，以中位数作为新左偏树的代表元素，如此如此。时间复杂度为 $ O(n\log n) $ 。 需要注意的是，这种解法对于 $ L_2 $ 问题有着更优秀的表现（线性），因为平均数远远比中位数好维护与合并。 解法三：考虑套上保序回归的板子并优化，容易发现跑网络流是完全多余的，只要枚举前多少个作为A号点，后面作为B号点即可，时间复杂度为 $ O(n\log w) $ 。 这三种解法实际上对于任意全序集均可以使用。 由此可见，保序回归的特殊形式问题往往拥有多样的解法。 补充一点，解法二能够解决的问题范围一般保序回归算法都能解决，但这不意味着维护折线法也是如此。例如[这题](https://www.luogu.com.cn/problem/P8476)，十分形似保序回归问题，但似乎只存在ds维护dp的解法，读者可自行进一步探究。 参考资料： [保序回归问题学习笔记 - ET2006](https://www.cnblogs.com/ET2006/p/bxhg.html) 南京外国语学校 高睿泉 浅谈保序回归问题 [题解 P6621 【[2020 年联考 A 卷] 魔法商店】- 灵梦](https://www.luogu.com.cn/blog/Hakurei-Reimu/solution-p6621)