BalticOI 2004 Sequence 题解

题目链接在这里~
对于序列\(\{a\}\)，把每一个\(a_i\)减去一个\(i\)，得到\(\{a'\}\)序列\(\{b\}\)同理。
因为\(b_1<b_2<...<b_n\)，故\(b_1'\leqslant b_2'\leqslant ... \leqslant b_n'\)
又\(a_i-b_i\)不变，故新问题与原问题等价。
因此我们就把问题就转化成了一个单调不下降序列。

我们将\(\{a_1, a_2, ..., a_m\}\)序列分成两段\(a_1...a_n\)\(a_{n+1}...a_m\)
假设\(b_1=b_2=...=b_n=u，b_{n+1}=b_{n+2}=... = b_{m}=v\)

则这个问题就变成了经典的邮递员问题，即货仓选址问题。

分类讨论：

1. \(u\leqslant v\)，则前半段取\(u\)，后半段取\(v\)即为最优解。
2. \(u > v\)，则\(\frac{u+v}{2}\)（\(u,v\)的中位数）为最优解，用左偏树实现。
   得到了中位数之后还需要下压.
   那么其中有两种情况. 奇数个数的中位数, 和偶数个数的中位数(为了方便用cost表示a和b的差值的绝对值):
   1 奇数个数的中位数的时候就只能选这个中位数, 然后无论再往上或者往下压的cost都得增加至少1. 那么如果这个中位数的解如果不小于再往前一段的解的话, 则可以结束. 若小于, 则需要再往前合并找中位数循环直到结束
   2 偶数个数的中位数. 那么可以在中间2个数之间上下浮动：
   a. 如果再往前一段的解在这2个数之间, 则取再往前一段的解即可. 否则如果往上虽然不增加cost但是还能下压, 往下的话就得继续合并前一段增加cost.
   b. 如果再往前一段的解小于这个区间, 则直接选这2个数里面小的即可
   c. 如果再往前一段的解大于这个区间, 则还是选这2个数里面小的, 然后再往之前合并

code

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 1e6 + 10;

int n, v[N], dist[N], l[N], r[N], ans[N], tt;
ll res;

struct Segment{int end, root, size;}stk[N];

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (v[x] < v[y]) swap(x, y);
    r[x] = merge(r[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){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;
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        auto cur = Segment({i, i, 1});
        dist[i] = 1;
        while (tt && v[cur.root] < v[stk[tt].root])
        {
            cur.root = merge(cur.root, stk[tt].root);
            if (cur.size % 2 && stk[tt].size % 2) cur.root = pop(cur.root);
            cur.size += stk[tt].size, tt -- ;
        }
        stk[ ++ tt] = cur;
    }

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

    for (int i = 1; i <= n; i ++ ) res += abs(v[i] - ans[i]);
    printf("%lld\n", res);
    for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i] + i);

    return 0;
}