从 分级 一题的更优做法谈保序回归问题

给一个序列$y_i$.你要求一个序列$f_i$. 给一个DAG描述一个偏序关系,若有$u\rightarrow v$的路径,则要求$f_u\le f_v$. 给定$p$,最小化:
$$ \sum_{i=1}^n|f_i-y_i|^p(1\le p<\infty)\\\\ \max_{i=1}^n|f_i-y_i|(p=\infty) $$
此类问题称为$L_p$问题,也称为 保序回归问题

定义 一个集合$S$的$L_p(1\le p<\infty)$均值为最小化$\sum_{x\in S}|k-y_s|^p$的$k$.

分级 (acwing 273)

给定一个序列$A$.构造一个非严格单调增(或非严格单调减)的序列$B$,最小化$\sum_{i=1}|A_i-B_i|$

原范围$n\le 2000$,可做到$n\le 3\times10^5$

首先我们只处理非严格单调增,因为非严格单调减只需将序列翻转后再做一次.那么我们只需处理序列上的$L_1$问题.

性质:集合$S$的中位数是其$L_1$均值(之一).

引理:对于序列上的$L_p(1\le p<\infty)$问题,若有$y_i>y_{i+1}$那么一定存在一组最优解$F$满足$f_i=f_{i+1}$

$L_1$时候证明很容易,若有$f_i<f_{i+1}$那么将$f_i$改为$f_{i+1}$会更优.

那么我们得到如下解法:

1. 维护一个单调栈,保存形如$(l,k)$的二元组,表示一个左端点在$l$的区间(右端点不必存,就是下一个左端点-1),且$f$值均为$k$.
2. 从左往右对于每个$i$,在栈顶加入$(i,a_i)$,若栈顶两个元素$(l_1,k_1),(l_2,k_2)\ (l_1<l_2)$不满足 $k_1\>k_2$那么将他们都弹掉,并将$(l_1,k’)$加入栈顶($k’$为$[l_1,i]$的$L_1$均值).

用主席树求区间的中位数,即可做到$O(n\log n)$的复杂度.

参考代码

剩余内容先鸽着吧,以后再补.

参考文献:

高睿泉, 浅谈保序回归问题, 国家集训队2018论文集