1.前言
这个东西其实就是把国家集训队的论文照抄下来，但是由于作者会加一些自己的理解（相当于是加注释），希望能让原本晦涩的论文好懂一些，也方便自己复习。
2.保序回归问题
偏序关系
设 ，这个柿子和 \(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\) 了。