题目地址:https://www.acwing.com/problem/content/2727/

　　分析：

（利用最优解的情况不唯一）
1.将问题转化成非下降子序列的绝对值之和
2.考虑序列的值相同的情况，中位数为最优解（贪心）
3.考虑两端前一段为值为u的序列后一段为值为v的序列，如果前一段大于等于后一段
那么这两端满足非降序列可以直接合并

结论：存在一组全段全部相等的解，且这个解一定不比最优解差

将问题变成求非下降子序列

对于a1,a2,a3,...,an
->a1 - 1,a2 - 2,...,an - n
将{bi} - >{bi - i}

对于b1 < b2 < b3 < ... < bn
b1 - 1 <= b2 - 2 <= ...<= bn - n

由于原序列bi - b(i - 1) >= 1 --> (bi - i) - (b(i-1) - (i - 1)) <= 0

所以{bi - i} 是一个非下降序列（可以相等不是严格的）

对与任意一个严格上升序列都可以求一个{bi - i}的非下降子序列

对于|ai - bi| = |(ai - i) - (bi - i)|

将构造后的新的a序列分成几段来考虑
这里先考虑分成两段的情况

假设券后两段的序列最优解分别为{b} {b'} 其中b = u,b' = v（u是前半段a系列的中位数，v是后半段a序列的中位数）

只考虑只考虑最优解的是相同值的情况，两段b序列是相同值的情况，那么这种解是所有解中的子集
现在要求这个子集的最优解，那么可以转化到货仓选址问题
对于一个序列求一个值使得这个值和序列中的所有值之差的绝对值之和最小
那么这个数一定是中位数

(1)如果u<=v那么这两段序列合并后是满足非降序列的，那么前半段取u后半段取v
一定是这种情况的最优解，假设前半段的绝对值之和的最小值是A后半段的绝对值之和的最小值是B那么合并后的序列的最优解前边短一定是大于等于A的，后半段一定是大于等于B的
所以合并后整体的最优解一定是大于等于A+B的，而等于A+B的情况是可以取到的就是前半段取u后半段取v 所以 最优解就是前半段取u后半段取v

如果u > v
那么和并后就不能原封不动的取u和v了因为这样就不满足条件了，假设两段合并后新的最优解一定是合并后的a序列的中位数
假设这两段a序列合并后的最优解是{b1,b2,b3,...,bm},将这个合并后的最优解按照u和v的分法也分成两段{b1,b2,...,bn} {bn+1,bn+2,...,bm}
这两段序列有一个性质bn <= u ,bn+1 >= v(最优解可能不是这样，因为最优解有多个但是一定存在满足这种性质的最优解)
证明如果bn > u，那么后半段{bn+1,bn+2,...,b一定在u的上面（这是一个非降序列），那么一定可以用序列u替换掉{b1,b2,...,bn}，（由于系列u也是最优解，替换掉之后最优解一定不会变差），第二段同理
如果bn+1<v的话那么前半段一定小于v那么后半段{bn+1,bn+2,...,bm}一定可以用v来代替答案不会变差
所以bn <= u ,bn+1 >= v

有着中条件后，先看后面一段（前面一段是对称的）

假设后半段的最优解为一段仙童的值，值为u，对于某一组完全在u上面的解{b1,b2,b3,...,bn}，将这一个解序列{b1,b2,b3,...,bn}全部替换成b1到u之间的某一个定值值，答案不会变差

数学归纳法：
固定b1段，将后面的段整体下移，至b2段达到段的为值其他的下移相同的距离x，对于b2及往后的字段对应的a序列的中位数一定是小于等于u的不然如果大于u了，假设是W，W>u那么b2及
往后的字段对应的a序列的最优解就不是取u了（满足非降了所以可替换），那么后半段至少有一半的a在u的下面，所以对于这一班a来说向下移这些a的绝对值之合一定是变小的，即至少有一半项减x
对于另一半最多也是增x答案不会变差，每一次嫌少一段后面的向下移，最后所有数都压到b1的位置整体不会变差，继续压到b1到u之间的数解过也不会变差
利用货仓选址问题的证明，u是中位数x为选址x越靠近中位数绝对值之和的结果会越小

结论：对于一段a序列的最优解是u，对于U任意一组该段的解 {b1,b2,b3,...,bn}，将这组解中的任意一个bi替换成b1到u之间的任意一个取值结果都不会变差

那么回到两段的第二种情况已知bn <= u ,bn+1 >= v ，那么将{b1,b2,b3,...,bn}全部替换成bn（对称），将{bn+1,bn+2,...,bm}全部替换成bn+1，又由于上述结论，将两两段分辨向u和v移动
直到持平（结果不会变差）就得到一组权段的值都相同的解，那么移动存在一组最优写是全段相同的，既然全段的值都相同那么这个值必定取这两段和并的a序列的中位数，这组解的构造方式如上
所以第二钟情况取中位数

根据上面的证明可以得到如下做法
将每一个单独的数看成一段每次加入一个数（相当于加入一段序列）。假设前面已经求出最优解了，最优解的序列是一段一段的（单个数也可以看成一段）（前一段一定是小于等于后一段的）
如果加入的新段大于等于前面一段那么就不管它直接加入到最优解的序列中（因为这样这一段的绝对值之和是0的并且满足非下降的条件）

如果新加入的一段小于前面一段那么利用情况二的方式将这两段删除加入和这两段长度之和相同的对应并且数值为这两段序列对应的a序列合并后的序列的中位数，如果合并后的新段还是小于前一段
那么重复刚刚的操作直到大于等于上一段为止

最后就等到一些非降的子段，每一个字段都是对应a序列的最优解，根据情况1所有a系列和并后的最优解就是这些字段的合并

左偏树的作用就是维护中位数

如何用左偏树维护中位数：
只维护较小一半数，这样半数的最大值一定是中位数，新段的中位数也使用左偏树维护一半的数
正常情况下用这种方法维护合并两段的中位数是不正确的，首先合并的情况只会发生在新段的中位数v小于前一段的中位数u
所以新的中位数一定是上一段的v到u范围内的数（被上一段的左偏树维护），以及新段的v到u部分的数（没有被新段的左偏树维护）所以是不正确的

但是由于每次新加入一段是一个数所以新段v到u中间是没有数的所以可以直接合并，那么合并后还是小于上一段呢
由于加上新数之前的段是大于他的但是加上后就小于他了，由于只增加了一个数所以中位数只会在相邻大小的数之间变化，相邻两个数之间是没有数的所以这也是正确的

 

细节：如果前一段区间有4 个元素后裔段区间有3个元素 前面左偏树维护2个元素，后一段左偏树维护2个元素和并后维护4个元素正好是7个元素的中位数

　　　如果前一段区间有4 个元素后裔段区间有4个元素 前面左偏树维护2个元素，后一段左偏树维护2个元素和并后维护4个元素总区间元素有8个所以可以任意维护中间两个都可（货仓选址）

　　　如果前一段区间有3 个元素后裔段区间有4个元素前面左偏树维护2个元素，后一段左偏树维护2个元素和并后维护4个元素正好是7个元素的中位数

　　    如果前一段有3个后一段也有3个元素，和并后左偏树维护4个元素，左偏树最大值维护的就不是中位数所以需要删除最大值

　　综上当两段区间大小都为奇数时需要删除元素

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 1000010;
int l[N],r[N],dist[N],idx;
LL v[N];
struct Segment
{
    int sz,end,root;
}stk[N];
int n;
LL a[N],ans[N];

int merge(int x,int y)
{
    if(!x || !y) return x + y;
    if(v[y] > v[x]) swap(x,y);
    r[x] = merge(r[x],y);
    if(dist[r[x]] > dist[l[x]]) swap(l[x],r[x]);
    dist[x] = dist[r[x]] + 1;
    return x;
}

int pop(int x)
{
    return merge(l[x],r[x]);
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&a[i]);
        a[i] -= i;
    }
    v[0] = -2e9;
    int tt = 0;
    for(int i = 1;i <= n;i ++)
    {
        v[i] = a[i];
        l[i] = r[i] = 0;
        dist[i] = 1;
        auto ver = Segment({1,i,i});
        while(tt && v[ver.root] < v[stk[tt].root])
        {
            ver.root = merge(ver.root,stk[tt].root);//记得改变root
            if(ver.sz % 2 && stk[tt].sz % 2)
                ver.root = pop(ver.root);
            ver.sz += stk[tt].sz;
            tt--;
        }
        stk[++tt] = ver;
    }
    LL res = 0;
    for(int i = 1,j = 1;i <= tt;i ++)
    {
        while(j <= stk[i].end)
        {
            ans[j] = v[stk[i].root];
            j ++;
        }
    }
    for(int i = 1;i <= n;i ++) res += abs(a[i] - ans[i]);
    printf("%lld\n",res);
    for(int i = 1;i <= n;i ++) printf("%lld ",ans[i] + i);
    return 0;
}