题目地址：洛谷：【P4331】[BOI2004]Sequence 数字序列 – 洛谷、BZOJ：Problem 1367. — [Baltic2004]sequence

题目描述

输入输出格式

输入格式：

输出格式：
第一行输出最小的绝对值之和。
第二行输出序列 bi ，若有多种方案，只需输出其中一种。

输入输出样例

输入样例#1：

5
2 5 46 12 1

输出样例#1：

47
2 5 11 12 13

说明

【数据范围】
40%的数据 n≤5000
60%的数据 n≤300000
100%的数据 n≤1000000 , 0≤a_i≤2×10^9

题解

考虑当所求序列$z_i$是不降的情况应该如何解决。我们有两种情况：

1. $t_1 \leq t_2 \leq \cdots \leq t_n$：$z_i=t_i$即可
2. $t_1 \geq t_2 \geq \cdots \geq t_n$：取这些值的中位数作为所有的$z_i$值，这是由于取中位数的时候可以证明答案最小

因此，我们可以将$t$数列分为若干区间，每个区间的答案即其中位数，从而解决这个问题。
然而题目让我们求一个严格递增的序列，我们考虑将$t_i$处理成$t_i – i$，就可以用跟上面一致的方法解决这个问题，因为处理完毕后的数列不降等价于原数列单增。
实现上，我们对每个元素建一个可并堆，然后向左合并左边元素构成的可并堆（即左边的区间），直到这个区间的中位数不小于左边相邻区间的中位数。中位数可以利用大根堆维护，让堆的大小不大于$\left\lceil \frac{|S|}{2} \right\rceil$再取堆顶即可。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

int n, a[MAXN];

struct Node {
    int ch[2], fa, val, dis, siz;
} tr[MAXN];
int rt[MAXN], l[MAXN], r[MAXN], htot;

inline int merge(int x, int y) {
    if(!x || !y) return x + y;
    if(tr[x].val < tr[y].val) std::swap(x, y);
    tr[x].ch[1] = merge(tr[x].ch[1], y);
    tr[x].siz = tr[tr[x].ch[0]].siz + tr[tr[x].ch[1]].siz + 1;
    tr[tr[x].ch[1]].fa = x;
    if(tr[tr[x].ch[0]].dis < tr[tr[x].ch[1]].dis) std::swap(tr[x].ch[0], tr[x].ch[1]);
    tr[x].dis = tr[tr[x].ch[1]].dis + 1;
    return x;
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint() - i;
    }
    for(int i = 1; i <= n; i++) {
        htot++; rt[htot] = i;
        l[htot] = r[htot] = i;
        tr[i].val = a[i]; tr[i].siz = 1;
        while(htot > 1 && tr[rt[htot]].val < tr[rt[htot - 1]].val) {
            htot--;
            rt[htot] = merge(rt[htot], rt[htot + 1]);
            r[htot] = r[htot + 1];
            while(tr[rt[htot]].siz * 2 > r[htot] - l[htot] + 2) {
                rt[htot] = merge(tr[rt[htot]].ch[0], tr[rt[htot]].ch[1]);
            }
        }
    }
    LL ans = 0;
    for(int i = 1; i <= htot; i++) {
        int w = tr[rt[i]].val;
        for(int j = l[i]; j <= r[i]; j++) {
            ans += abs(w - a[j]);
        }
    }
    printf("%lld\n", ans);
    for(int i = 1; i <= htot; i++) {
        int w = tr[rt[i]].val;
        for(int j = l[i]; j <= r[i]; j++) {
            printf("%d ", w + j);
        }
    }
    return 0;
}