数字序列问题

解题思路

我们要构造出一个严格递增的序列 $b_i$，使得两个序列各项之差的绝对值之和最小。

这里令 $a_i’ = a_i-i$，令 $b_i’=b_i-i$，由于 $b_1<b_2<…<b_n$，所以 $b_i-b_{i-1}\geq 1$，因此 $b_i’-b_{i-1}’=b_i-i-\big(b_{i-1}-(i-1)\big)=b_i-b_{i-1}-1 \geq 0$，所以 $b_1’\leq b_2’ \leq … \leq b_n’$

对于我们构造的任意一个非严格递增的序列，我们都能转化回去得到一个严格递增的序列。而且此时 $\vert a_i’- b_i’ \vert = \vert a_i-b_i \vert$，这样我们就将问题从构造一个严格递增的序列变成了构造一个非严格递增的序列。

这里考虑一种特殊情况，假设存在一种构造方案，使得 $a_1 \sim a_m$ 中每个数都取 $u$，$a_{m+1} \sim a_n$ 中每个数都取 $v$。

我们将整个构造序列分成两段，现在我们要考虑每一段数取相同值，使得整个序列各项之差的绝对值之和最小。而这两段每一段其实就是一个货仓选址问题，我们只需要各取每一段的中位数作为这两段的值就能让这两段的差值最小。

若 $u \leq v$，假设前面半段的最优解的和是 $A$，后半段的最优解的和是 $B$，则整个序列的最优解的和就是 $A+B$，而前半段取 $u$ 最终的和 $S_u \geq A$，后半段取 $v$ 最终的和 $S_v \geq B$，则整个的解为 $S_u+S_v\geq A+B$，所以下限是最优解，且可以取到最优解，所以最小值就是 $A+B$

若 $u \geq v$，此时前半段的值大于后半段的值，整个序列就不是递增的了，此时一定存在一组最优解，使得 $b_m \leq u$，如果此时 $b_m > u$，由于 $u$ 是前半段的最优解，因此我们可以把 $b_1 \sim b_m$ 都变成 $u$，就能满足 $b_m \leq u$，同理，也存在一组最优解，使得 $b_{m+1} \geq v$，如果 $b_{m+1} < v$，那么我们就可以把后半段全部替换成 $v$，就能满足 $b_{m+1} \geq v$。

此时我们只看后半段，这里有一个特性就是如果我们将 $b_{m+1} \sim b_n$ 都替换成 $u \sim b_{m+1}$ 之间的某一个值，结果不会变差。假设此时给我们的这组解有 $k$ 段，此时我们试图将 $b_{m+1} \sim b_n$ 都变成第一段的值，第一段显然不用动，但是后面 $k-1$ 段都需要下压到第一段的位置。此时我们将后面 $k-1$ 段都向下移动 $x$ 的距离，假设此时后面 $k-1$ 段的中位数是 $w$，而 $w \leq u$，如果 $w>u$，则后面这 $k-1$ 段取 $w$ 则答案会变得更好，这就与 $u$ 是最优解矛盾了，所以 $w \leq u$，这就意味着后面 $k-1$ 段中至少有一半的数是 $\leq u$ 的，而这一半我们将 $b_i$ 往下移其实是拉近他们的距离，意味着至少有一半项的差是会减少 $x$ 的，而剩余的一半项的差最多会加 $x$，不可能比 $x$ 多，因此将后面 $k-1$ 段整体向下移动 $x$ 后结果一定不会变大。移完之后我们就将第二段移到了第一段的位置，然后我们继续将后面 $k-2$ 段向下移，最终能将所有 $k$ 段压到第一段的值，并且答案不会变差。此时所有段都在第一段后，然后我们再将所有段从第一段的值再继续往下移，搭配货舱选址问题的思考，如果我们不断往上移，则答案一定会一直变差，反过来如果我们不断往下移，则答案一定会一直变好。到此就能证明我们将 $b_{m+1} \sim b_n$ 的任何一组解替换成 $u \sim b_{m+1}$ 中的任何一个值结果都不会变差。而对于前半段也是同理的，让我们将 $b_1 \sim b_m$ 的任何一组解替换成 $b_m \sim u$，结果也不会变差。注意，前半段是上移不会变差，后半段是下移不会变差，结论对称。

因此对于 $b_1 \sim b_n$ 的任何一组解，我们将前半段先替换成 $b_m$，将后半段先替换成 $b_{m+1}$，此时由于 $b_i$ 一定是非下降的，因此前半段应该在后半段的下面，我们再将前半段上移到和后半段相同的位置，此时前半段和后半段就相等了，这就证明了当 $u \geq v$ 时，一定存在一组全段相等的解，并且不比最优解差。这就意味着存在一组全段相等的最优解。而如果全段都取一个固定值的话，那必然是取中位数才可以取到最优解。因此当前半段的中位数大于后半段的中位数时，必然存在一组解是取整段的中位数的。

当以上两个结论成立后，我们就可以从前往后枚举每个数，对于每个数，我们将他看作一个单独的段，此时前面应该也是一段一段的区间，由于当前区间只有一个数，因此取的中位数肯定就是他自己，此时如果它比前一段的中位数要大，那么根据第一个结论，此时的方案是合理的，我们不用管他，继续考虑后面的数。如果它比前一段的中位数要小，那么根据第二个结论，此时这两段应该取他们两个中位数的中位数，此时这两段取的值相同的，等于是合并成了一整段，然后那新合并的段继续和前一段进行比较，如果小了继续合并，直到新合并的段比前一段大了，此时方案就合法了，不需要再合并，再继续考虑后面的数。

最终我们考虑完了所有的数，并且所有数分成了一段一段的区间，每个区间中取的值相同，并且所有区间取的值是非下降的，而每一段的取值都是让这一段的所有数之差的绝对值之和最小的最优解，那么整个序列的最优解就是每一段的最优解的和。

接下来我们只需要按照以上思路用每一段的中位数来进行合并，最终得到一个非下降的序列，就是答案的解。这里我们需要维护每一段区间的中位数，而维护一段区间的中位数是可以用堆来维护的，这里要维护多个区间，也就是维护多个堆，因此需要用到左偏树来维护所有的堆，美与每个区间，我们可以用堆来维护较小的一半数，则较小的一半数中最大的数就是该区间的中位数。但是当我们合并两个区间时，由于只有前一段的中位数小于后一段的中位数时才需要维护，假设前一段的中位数是 $u$，后一段的中位数是 $v$，显然 $v < u$，由于前一段一半的数都 $< u$，后一段一半的数都 $< v < u$，因此新的中位数一定 $< u$，同理可证新的中位数一定 $> v$。因此新的中位数一定在 $v \sim u$ 之间，此时中位数如果取前一段中 $v \sim u$ 中的某一个数，那么此时这个数就被维护在前一段的堆中，我们是可以直接取的，但是新的中位数同样有可能取到后一段中 $v \sim u$ 中的某一个数，但是后一段我们只维护了较少的一半数，也就是 $0 \sim v$ 之间的数，并没有维护 $v \sim u$ 中的某一个数，那么此时我们就取不到真正应该去的新的中位数，结果就会出错。

但是本题有点特殊，由于我们是一个数一个数的枚举的，每次只将一个数加入到解中，如果当前区间比前一个区间高，则不用合并。如果当前区间比前一个区间低，此时我们就需要将两个区间合并，假设前一个区间的中位数是 $u$，当前区间的中位数是 $v$，合并后新的中位数应该在 $v \sim u$ 之间，此时我们只加入了一个数，也就是说当前区间中只有一个数，如果中位数在前一段区间中是没有任何问题的，一定取得到，如果中位数在当前区间中，看似我们取不到 $v \sim u$ 之间的数，但是由于当前区间只有一个数，因此如果中位数在当前区间中，$u$ 和 $v$ 我们又不可能是新的中位数，此时当前区间中不存在任何可能取到的中位数，这就恰好规避到了我们刚刚分析时遇到的问题。所以这个问题的特殊性帮我们处理掉了这种边界情况。

而如果不是插入的时候，我们需要真正的将当前段和前一段合并，当前段不再只有一个数了，此时的情况应该是当前区间刚插入了一个数，然后和前一段区间合并，假设最开始中位数是 $v$，则插入一个数之后中位数 $w$ 一定 $< v$，而此时再合并前一段区间，则如果中位数在当前区间中，那么一定是在 $w \sim v$ 之间的，但是我们知道，由于只插入一个数，因此中位数最多只会变成原中位数前面的一个相邻元素，因此此时 $w \sim v$ 之间是没有任何元素的，所以也不存在新中位数在当前区间中的情况，也恰好规避掉了这个问题。

因此没有了这个问题之后，我们就可以用左偏树来维护所有中位数了，这里维护的是大根堆，每次合并的时候只需要将堆合并再取新的堆的最大值就是新的中位数。然后就可以按照上述思路得到答案。（这题的思路我只能说麻了~）

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010;

struct Segment
{
    int end, root, cnt; //终点、根节点、大小
}stk[N]; //用栈存储每段区间
int tt;

int n;
int v[N], dist[N], l[N], r[N], idx; //左偏树
int res[N]; //记录答案

int merge(int x, int y) //将 x 和 y 所在的左偏树合并，并返回合并后的根节点
{
    if(!x || !y) return x + y;
    if(v[x] < v[y]) swap(x, y); //保证 x > y，则 x 是合并后根节点
    r[x] = merge(r[x], y); //将 x 的右子树和 y 合并
    if(dist[r[x]] > dist[l[x]]) swap(r[x], l[x]); //保证左子树的距离 > 右子树的距离
    dist[x] = dist[r[x]] + 1; //右子树发生改变，更新根节点的距离
    return x;
}

int pop(int x) //删除以 x 为根的左偏树的根节点，并返回删除后的根节点
{
    return merge(l[x], r[x]); //将左子树和右子树合并
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]); //最开始每个数就是一个大根堆
        v[i] -= i; //将严格单调上升转换成非严格单调上升
        dist[i] = 1;
    }

    tt = 0;
    for(int i = 1; i <= n; i++)
    {
        auto cur = Segment({i, i, 1}); //最开始每个数就是一个区间
        //如果当前区间的中位数 < 前一个区间的中位数，则需要将两个区间合并
        while(tt && v[cur.root] < v[stk[tt].root])
        {
            cur.root = merge(cur.root, stk[tt].root); //将两个区间合并
            //对于每个区间，为了保证堆顶是中位数，堆中应该存区间长度 / 2（上取整）
            //当两个区间的长度都是偶数时，合并后的堆的大小恰好是区间的一半
            //当两个区间的长度一个是奇数一个是偶数时，合并后的堆的大小恰好是区间的一半
            //当两个区间的长度都是奇数时，合并后的堆的大小比区间的一半多一个，此时需要弹出一个元素
            if(cur.cnt % 2 && stk[tt].cnt % 2) cur.root = pop(cur.root);
            cur.cnt += stk[tt].cnt; //更新合并后的区间的长度
            tt--; //将栈顶区间弹出
        }
        stk[++tt] = cur; //将当前区间加入栈
    }

    for(int i = 1, j = 1; i <= tt; i++)
    {
        while(j <= stk[i].end) res[j++] = v[stk[i].root];
    }

    LL sum = 0; //记录各项之差的绝对值之和
    for(int i = 1; i <= n; i++) sum += abs(v[i] - res[i]);
    printf("%lld\n", sum);
    for(int i = 1; i <= n; i++) printf("%d ", res[i] + i);

    return 0;
}