题目链接，参考资料：论文集2018《浅谈保序回归问题》高睿泉

保序回归问题的定义

$L_p$ 问题的定义如下：

$G=(V,E)$ $i$ $y_i,w_i$ $w_i>0$ $f$ $G$ $i$ $j$ $v_i\preceq v_j$ $f_i\le f_j$ ，并使得回归代价
$\begin{cases}\sum_{i=1}^nw_i|f_i-y_i|^p&(1\le p<\infty)\\\max_{i=1}^n w_i|f_i-y_i|&(p=\infty)\end{cases}$
最小。

其他定义

$z$ $\le a$ $a$ $\ge b$ $b$ ，称为 $z$ $(a,b)$ 取整。

$U$ $L_p$ 均值为使得
$\begin{cases}\sum_{i\in U}w_i|k-y_i|^p&(1\le p<\infty)\\\max_{i\in U} w_i|k-y_i|&(p=\infty)\end{cases}$
$k$ 。

$\bold S$ 问题 $L_p$ $a\le f_i\le b\ \ (a<b)$ ，求最小回归。

$p=1$ 情况的解法——整体二分

准备工作

引理 1. $1<p<\infty$ $U$ $L_p$ $p=1$ $U$ $L_p$ 均值构成一个区间。
引理 2. $L_p(1\le p<\infty)$ 均值不小于该集合的最小值，不大于该集合的最大值。

证明：设

g_U(k)=\sum_{y_i\le k,i\in U}w_i(k-y_i)^p+\sum_{y_i>k,i\in U}w_i(y_i-k)^p

则有

g'_U(k)=\sum_{y_i\le k,i\in U}pw_i(k-y_i)^{p-1}-\sum_{y_i>k,i\in U}pw_i(y_i-k)^{p-1}

$g'_U(k)$ $p>1$ $p=1$ $k<\min y$ $g'_U(k)<0$ $k>\max y$ $g'_U(k)>0$ $\square$

重要定理

定理 1. $L_1$ 问题中，如果：
$y_i$ $(a,b)$ 内
$z_i$ $(a,b)$ 内
$z^S$ $S$ $L_1$ $z$ $z$ $(a,b)$ $z^S$ 。

这个引理并没有它看起来那么自然。

证明：反证法。

$z^S$ $L_1$ $z$ $(a,b)$ $z_S$ 的最优解。

下面我们证明一个引理

引理 3. $\forall i,z_i^S=a\or z_i^S=b$ 。

证明： $g'$ $(a,b)$ $z_i^S\neq a\and z_i^S\neq b$ 。

$z_i^S\neq b$ $U$ $U$ $\le$ $g'_U\le 0$ $U$ $b$ $U$ $z^S$ $\square$

$z_i$ $z_i^S=b,z_i\le a$ $z^S_i=a,z_i\ge b$ 。

显然这两类点之间没有偏序关系，于是可以分开研究，从而我们接下来可以不失一般性地只证明

$z$ $z_i^S=b,z_i\le a$ $z$ 是最优解。

记这类点为坏点。

$z$ 取到最大值 $U$ 引理 1 $U$ $L_1$ $[l,r]$ $U$ $g$ $(-\infty,l)$ $(r,+\infty)$ 单调增。

（请注意，当我们谈论任何其他集合不成立的 $g$ $U$ $U$ 的所有元素一起调整。）

$z_U\in [l,r]$ $z_U$ $U$ $z$ 值。）

$U$ $z$ $z_i^S=b$ $U$ $\le$ 限制。

$l>a$ $U$ $z$ $l$ $z$ 并非最优解，得出矛盾。
$l\le a,b\le r$ $U$ $z$ $b$ $z^S$ $L_1$ 最优解，得出矛盾。
$l\le a,b>r$ $z_U$ $V$ 为坏点集合。
- $U=V$ $z^S_i,i\in V$ $b$ $z^S$ $S$ 问题的最优解，得出矛盾。
$W$ $V/U$ $z$ $W$ $L_1$ $[l',r']$ $U$ $W$ “卡住”。
- - $r'<b$ $z_i^S,i\in W$ $z^S$ $S$ 问题的最优解，得出矛盾。
- - $r'\ge b>a\ge z_U$ $z_W$ $z_U$ $\square$

解法

我们还需要一个引理

引理 4. $L_1$ $z$ $\forall z_i\in\{y\}$ 。

证明：引理 3 $\square$

整体二分 $y[l,r]$ $S\{y_{mid},y_{mid+1}\}$ 定理 1 $y[l,mid]$ $y[mid+1,r]$ 。

$1<p<\infty$ $p=1$

重要定理

定理 2. $L_p(1<p<\infty)$ 问题中，如果：
$L_p$ $(a,b)$ 内
$z_i$ $(a,b)$ 内
$\tilde z$ 是相同 DAG 上的，回归代价为
$(\tilde y_i,\tilde w_i)=\begin{cases}(0,w_i\Big((b-y_i)^p-(a-y_i)^p\Big))&(y_i\le a)\\(1,w_i\Big((y_i-b)^p-(y_i-a)^p\Big))&(y_i>a)\end{cases}$
$L_1$ $0,1$ $L_1$ $z$ $\tilde z_i=0\Leftrightarrow z_i\le a,\tilde z_i=1\Leftrightarrow z_i\ge b$ 。

证明： $L_1$ $S$ 问题等价。

$L_p$ $(a,b)$ 结论 1 $S$ $a,b$ 。

引理 3 $L_1$ $0,1$ 。

$\tilde w_i|\tilde y_i-0|=w_i|y_i-a|^p,\tilde w_i|\tilde y_i-1|=w_i|y_i-b|^p$ ，读者自证不难，从而得到等价。

定理 1 $\square$

解法

$(x,y)$ $L_p$ $n$ $z_{i1}=z_{i2}=...$ $L_p$ 均值，运用引理 1~~看起来~~ $\varepsilon$ $b=a+\varepsilon$ $\tilde w_i$ $a$ 处回归代价的导数。于是在实数上二分即可。

技巧和例题

偏序关系是一条链的情况

引理 5. $y_i>y_{i+1}$ $f_i=f_{i+1}$ 。

证明：显然。

$L_p$ ~~去世了~~ $L_p$ 均值即可。

$L_p(p>1)$ $L_2$ $L_1$ $O(\log n)$ $\log^2 n$ 也行。

[BalticOI 2004]Sequence 数字序列

$a_i\leftarrow a_i-i$ $L_1$ 问题。应用上面的解法即可。

这里的实现没有对每个区间都维护两个堆，而是只记一个，进入另一个假想的堆的元素直接销毁。相信你仔细想想就能明白这是为什么。


x
#include<bits/stdc++.h>
using namespace std;
struct leftist{
    int c[2];
    int dis, val;
    int siz;
} H[100005];
void pushup(int x) {
    if (H[H[x].c[1]].dis < H[H[x].c[0]].dis) swap(H[x].c[0], H[x].c[1]);
    H[x].dis = H[H[x].c[0]].dis + 1;
    H[x].siz = H[H[x].c[0]].siz + H[H[x].c[1]].siz + 1;
}
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (H[x].val < H[y].val) swap(x, y);
    H[x].c[0] = merge(H[x].c[0], y);
    pushup(x);
    return x;
}
int n;
struct node {
    int rt;
    int true_siz;
    int val;
};
node stk[100005]; int len;
int tgt[100005];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        H[i].dis = 1, scanf("%d", &H[i].val), H[i].val -= i, H[i].siz = 1;
    for (int i = 1; i <= n; i++) {
        stk[++len] = (node){i, 1, H[i].val};
        while (len != 1 && stk[len - 1].val > stk[len].val) {
            len--; stk[len].rt = merge(stk[len].rt, stk[len + 1].rt);
            stk[len].true_siz += stk[len + 1].true_siz;
            while (H[stk[len].rt].siz > (stk[len].true_siz + 1) / 2)
                stk[len].rt = merge(H[stk[len].rt].c[0], H[stk[len].rt].c[1]);
            stk[len].val = H[stk[len].rt].val;
        }
    }
    int cnt = 0, pos = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt == 0) cnt += stk[++pos].true_siz;
        cnt--;
        tgt[i] = pos;
        ans += abs(H[i].val - stk[pos].val);
    }
    printf("%lld\n", ans);
    for (int i = 1; i <= n; i++) printf("%d ", stk[tgt[i]].val + i);
}

[HNOI2019]序列

要分数取模的最优化问题，已经完全暴露了啊（

$L_2$ 问题，但是需要支持特殊询问。

由于最优解显然和我们的单调栈扫描顺序无关，从而我们可以处理出一个元素前缀和后缀的单调栈情况。（可以考虑主席树；其实把询问离线，从左到右扫时暴力把右栈回退也可以）

$x$ $x$ $x$ $x$ 所在的区间。

$L$ $R$ $R$ 套在外面二分即可。


xxxxxxxxxx
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 100005, p = 998244353;
int norm(int x) { return x >= p ? x - p : x; }
int inv[maxn];
void init() {
    inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = 1LL * (p - p / i) * inv[p % i] % p;
}
struct frac {
    ll a;
    int l, r;
    frac operator + (const frac v) const { return (frac){a + v.a, l, v.r}; }
    bool operator < (const frac v) const {
        return (__int128)a * (v.r - v.l + 1) < (__int128)v.a * (r - l + 1);
    }
} suf[maxn], pre[maxn];
int suf_val[maxn], pre_val[maxn];
int ls, lp;
vector<frac> his_del[maxn];
int n, m;
int A[maxn];
ll S1_[maxn];
int S1[maxn], S2[maxn];
frac newfrac(int l, int r, int del = 0) { return (frac){S1_[r] - S1_[l - 1] + del, l, r}; }
int inline getS1(int l, int r) { return norm(S1[r] - S1[l - 1] + p); }
int inline getavg(int l, int r) { return 1LL * getS1(l, r) * inv[r - l + 1] % p; }
int inline getS2(int l, int r) { return norm(S2[r] - S2[l - 1] + p); }
int inline getVAL(int l, int r) {
    int avg = getavg(l, r);
    ll ans = getS2(l, r) - 2LL * avg * getS1(l, r) + 1LL * avg * avg % p * (r - l + 1);
    return norm((int)(ans % p) + p);
}
struct qry {
    int val, id;
}; vector<qry> Qs[maxn];
int ans[maxn];
int get_L(int del, int R) {
    int xL = 0, xR = lp;
    while (xL < xR) {
        int mid = (xL + xR + 1) >> 1;
        if (pre[mid] < newfrac(pre[mid].r + 1, R - 1, del)) xL = mid;
        else xR = mid - 1;
    }
    return xL;
}
pair<int, int> get_R(int del) {
    int xL = 0, xR = ls;
    while (xL < xR) {
        int mid = (xL + xR + 1) >> 1;
        int L = get_L(del, suf[mid].l);
        if (newfrac(pre[L].r + 1, suf[mid].l - 1, del) < suf[mid]) xL = mid;
        else xR = mid - 1;
    }
    return make_pair(get_L(del, suf[xL].l), xL);
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]),
        S1_[i] = S1_[i - 1] + A[i],
        S1[i] = (S1[i - 1] + A[i]) % p,
        S2[i] = (S2[i - 1] + 1LL * A[i] * A[i]) % p;
    for (int i = 1; i <= m; i++) {
        int pos, val;
        scanf("%d%d", &pos, &val);
        Qs[pos].push_back((qry){val - A[pos], i});
    }
    suf[0] = (frac){1, n + 1, n};
    for (int i = n; i; i--) {
        frac now = (frac){A[i], i, i};
        while (ls && suf[ls] < now) {
            his_del[i].push_back(suf[ls]);
            now = now + suf[ls--];
        }
        suf[++ls] = now;
        suf_val[ls] = norm(suf_val[ls - 1] + getVAL(now.l, now.r));
    }
    ans[0] = suf_val[ls];
    for (int i = 1; i <= n; i++) {
        ls--;
        for (int j = his_del[i].size() - 1; j >= 0; j--) {
            suf[++ls] = his_del[i][j];
            suf_val[ls] = norm(suf_val[ls - 1] + getVAL(suf[ls].l, suf[ls].r));
        }
        for (qry e : Qs[i]) {
            pair<int, int> qaq = get_R(e.val);
            ans[e.id] = norm(pre_val[qaq.first] + suf_val[qaq.second]);
            int l = pre[qaq.first].r + 1, r = suf[qaq.second].l - 1;
            // printf("%d %d\n", l - 1, r + 1);
            int avg = 1LL * norm(getS1(l, r) + e.val) * inv[r - l + 1] % p;
            ll tmp = getS2(l, r) - 1LL * A[i] * A[i] + 1LL * (A[i] + e.val) * (A[i] + e.val);
            tmp = norm((int)(tmp % p) + p);
            tmp -= 2LL * avg * norm(getS1(l, r) + e.val);
            tmp += 1LL * avg * avg % p * (r - l + 1);
            tmp = norm((int)(tmp % p) + p);
            ans[e.id] = norm(ans[e.id] + (int)tmp);
        }
        frac now = (frac){A[i], i, i};
        while (lp && now < pre[lp])
            now = pre[lp--] + now;
        pre[++lp] = now;
        pre_val[lp] = norm(pre_val[lp - 1] + getVAL(now.l, now.r));
    }
    
    for (int i = 0; i <= m; i++) printf("%d\n", ans[i]);
}

网络流

$L_1:S$ $f_i\le f_j$ $f_i$ $f_j$ ，变为最大权闭合子图问题，是一个经典网络流例题。

[省选联考 2020 A 卷] 魔法商店

众所周知线性基是拟阵。考虑基交换引理：

$A,B$ $x\in A/B$ $y\in B/A$ $A/\{x\}\cup\{y\}$ 是一个基。

$A$ $B$ 变大。

$A$ $B$ ）中的元素和其外的元素，如果能互相替换就有偏序关系。

最后应用上保序回归就做完了！！！

$p=\infty$ 的情况和扩展

🕊了

保序回归问题的定义

其他定义

对 p=1 情况的解法——整体二分

准备工作

重要定理

解法

1<p<\infty 的情况——化归到 p=1

重要定理

解法

技巧和例题

偏序关系是一条链的情况

[BalticOI 2004]Sequence 数字序列

[HNOI2019]序列

网络流

[省选联考 2020 A 卷] 魔法商店

p=\infty 的情况和扩展

$p=1$ 情况的解法——整体二分

$1<p<\infty$ $p=1$

$p=\infty$ 的情况和扩展