保序回归

问题

为每个点选择一个权值 \(f_i\)，满足若干条限制：\(f_u \le f_v\)，目的是最小化 \(\sum\limits_{i=1}^{n} w_i \cdot |f_i - b_i| ^ k\)。

\(k = 1\)

首先有引理：

若强制所有 \(f_i \in [l,l+1]\)，则一定存在某种最优解满足若当前最优解 \(now_i = l\) 则 \(f_i \le l\)，\(now_i = l + 1\) 则 \(f_i \ge l + 1\)。

据此整体二分即可。注意到若 \(u\) 和 \(v\) 递归到了无交的区间则限制一定已经满足，则只用关心当前集合即可。

构造当前最优解视情况而定，通用的方法是最大权闭合子图，因为可以看做 \(u\) 选 \(mid+1\) 则 \(v\) 必须选 \(mid+1\)，收益是 \(val(mid+1) - val(mid)\)。

\(k \ge 2\)

问题在最优的 \(f_i\) 可能是小数。则只能要求 \(f_i \in [l, l + \epsilon]\)，直接把权值设为 \(val(mid + \epsilon) - val(mid)\) 精度会炸，设为 \(val\) 的导数即可。