1.前言

这个东西其实就是把国家集训队的论文照抄下来，但是由于作者会加一些自己的理解（相当于是加注释），希望能让原本晦涩的论文好懂一些，也方便自己复习。

由于我看得比较慢，所以这篇文章可能更新得很慢

2.保序回归问题

偏序关系

设 \(R\) 是集合 \(S\) 上的一个二元关系，若 \(R\) 满足：

• 自反性：\(\forall x\in S\)，有 \(x\space R\space x\)
• 反对称性：\(\forall x,y\in S\)，若有 \(x\space R\space y,y\space R\space x\)，则有 \(x=y\)
• 传递性：\(\forall x,y,z\in S\)，若有 \(x\space R\space y,y\space R\space z\)，则有 \(x\space R\space z\)

那么就称为 \(R\) 为 \(S\) 上的非严格偏序关系，记作 \(\preceq\)

这个东西感性理解一下就行，\(oier\) 谁管这些定义？

问题描述

我们有一张 \(n\) 个点的表示偏序关系的有向图，给定两个代价数组 \(y\) 和 \(w\)，每条边表示连接的两个点之间有直接的偏序关系，那么图上两个点满足 \(v_i\preceq v_j\) 当且仅当在图上有一条简单路径。

求数组 \(f\) 满足 \(\forall v_i\preceq v_j\)，都有 \(f_i\leq f_j\)，那么最小化回归代价：

对于 \(p\) 相同的保序回归，我们称之为 \(L_p\) 问题。

所以为什么要叫保序回归问题？因为他能在保证顺序（偏序关系）的情况下最小化回归代价

一些约定

将序列 \(z\) 中不超过 \(a\) 的元素变为 \(a\)，不小于 \(b\) 的元素变为 \(b\) 称为序列 \(z\) 向集合 \(S=\{a,b\}\) 取整

点集 \(U\) 的 \(L_p\) 均值为满足 \(\sum_{v_i\in U}w_i|y_i-k|^p(1\leq p<\infty)\) 或者 \(\max_{v_i\in U}w_i|y_i-k|\) 最小的 \(k\)

也就是如果一堆点非要选一个相同的 \(f\) 那么选哪个数会最好。

3.特殊情形下的算法

一种贪心算法

例一：题目描述

给定正整数序列 \(y,w\)，求单调不减的实数序列 \(f\)，最小化 \(\sum_{i=1}^nw_i(f_i-y_i)^2\)

\(n\leq 200000\)

例一：解法

本题的偏序关系就是 \(f_i\leq f_j\) 的一条链，先给出两个比较重要的结论。

结论1：点集 \(U\) 的 \(L_2\) 均值为其加权平均数 \(\frac{\sum_{v_i\in U}w_iy_i}{\sum_{v_i\in U}w_i}\)

直接把平方展开之后就是二次函数的最值点。

如果有凸单调性但是更为复杂的函数最值，说不定可以让导数为 \(0\) 然后反解出那个位置的 \(x\)

结论2：\(\forall 1\leq i<n\)，如果有 \(y_i>y_{i+1}\)，那么最优解一定有 \(f_i=f_{i+1}\)

证明用到了微调法和反证法，如果在最优解中 \(f_i<f_{i+1}\)，那么我们选择极小的 \(\epsilon>0\)，得到的 \(f_i’=f_i+\epsilon w_{i+1},f_{i+1}’=f_{i+1}-\epsilon w_i\)，你可能觉得这样微调有点奇怪，但是这样能让微调的变化取决于 \(y_i\) 和 \(y_{i+1}\) 的关系，展开就知道了：

虽然我不是很懂极限，这个柿子和 \(0\) 的关系取决于一阶无穷小的大小，那么微调后答案变小，所以矛盾。

回到这道题，我们考虑怎么利用这两个结论，由于 \(f\) 取等的条件是 \(y_i>y_{i+1}\)，那么我们可以维护关于 \(y\) 的单调不减的单调栈，如果已知一个集合中的点取的 \(f\) 是相同的，那么可以把这个集合合并为一个点考虑，最优取值就是其 \(L_2\) 均值，具体的算法流程是这样的：

• 维护一个单调栈，栈内的每个元素为 \((S_i,y_i’,w_i’)\)，分别表示这个元素代表的集合，这个集合的 \(L_2\) 均值，这个集合的 \(w_i\) 的求和。
• 每次就加入 \((\{i\},y_i,w_i)\)，如果有 \(y’_{top}>y_i\)，那么直接把这两个集合合并，新集合的 \(L_2\) 均值也可以很好地算出来，那么把原来的元素删除，再把 \((\{i\}|S_{top},\frac{y_i+y’_{top}}{w_i+w’_{top}},w_i+w’_{top})\) 加入单调栈中即可，然后继续看这个元素能不能弹出栈顶。
• 最后 \(f_i\) 就是集合包含 \(i\) 元素的 \(L_2\) 均值（也就是 \(y’_{x}\)）

上述算法的时间复杂度 \(O(n\log n)\)（因为好像要维护集合），如果能算出 \(L_p\) 均值那么是可以向 \(L_p(1\leq p<\infty)\) 扩展的。

这个算法的局限性在于结论 \(2\) 并不是一直适用的，如果换了一个偏序关系就 \(gg\) 了。