求める値 \(D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen\) について、この式から絶対値を外すことを考えます。

\[\begin{aligned} D _ i&=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen\\ &=\min\lbrace\min_{j\lt i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+i-j\right\rparen,\min_{j\gt i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+j-i\right\rparen\rbrace\\ &=\min\lbrace\min_{j\lt i,P _ j\lt P _ i}\left\lparen P _ i-P _ j+i-j\right\rparen,\min_{j\lt i,P _ j\gt P _ i}\left\lparen P _ j-P _ i+i-j\right\rparen,\min_{j\gt i,P _ j\lt P _ i}\left\lparen P _ i-P _ j+j-i\right\rparen,\min_{j\gt i,P _ j\gt P _ i}\left\lparen P _ j-P _ i+j-i\right\rparen\rbrace\\ &=\min\lbrace P _ i+i-\max_{j\lt i,P _ j\lt P _ i}\left\lparen P _ j+j\right\rparen,\min_{j\lt i,P _ j\gt P _ i}\left\lparen P _ j-j\right\rparen-\lparen P _ i-i\rparen,P _ i-i-\max_{j\gt i,P _ j\lt P _ i}\left\lparen P _ j-j\right\rparen,\min_{j\gt i,P _ j\gt P _ i}\left\lparen P _ j+j\right\rparen-\lparen P _ i+i\rparen\rbrace \end{aligned}\]

となり、\(A _ i=P _ i+i,B _ i=P _ i-i\) のように定めると、

\[\begin{aligned} D _ i&=\min\lbrace A _ i-\max_{j\lt i,P _ j\lt P _ i}A _ j,\min_{j\gt i,P _ j\gt P _ i}A _ j-A _ i,B _ i-\max_{j\gt i,P _ j\lt P _ i}B _ j,\min_{j\lt i,P _ j\gt P _ i}B _ j-B _ i\rbrace \end{aligned}\]

となります。

これは、セグメント木などの区間最大値（もしくは区間最小値）が得られるデータ構造を用い、\(i\) について走査しながら \(A _ i\) や \(B _ i\) を \(P _ i\) の位置に更新していくことで解くことができます。

実装例は以下のようになります。

いずれか \(1\) 通りについて解く関数を作り、列を反転させたり \(P _ i\leftarrow N+1-P_i\) などとすることで \(4\) 通りすべてをカバーするようにすると実装が単純になります。

#include <iostream>
#include <vector>
#include <atcoder/segtree>

using namespace std;

constexpr int INF = 100000000;

// 区間最大値を得るセグメント木の準備
using S = int;
int op(int a, int b) { return max(a, b); }
int e() { return -INF; }
using segtree = atcoder::segtree<S, op, e>;

void calc(const int N, const vector<int> &P, vector<int> &D) {
    // chmin(D[i], P[i] + i - max_{j < i && P[j] < P[i]} {P[j] + j}
    segtree segment_tree(N);
    for (int i = 0; i < N; ++i) {
        D[i] = min(D[i], P[i] + i - segment_tree.prod(0, P[i]));
        segment_tree.set(P[i] - 1, P[i] + i);
    }
}

int main() {

    int N;
    cin >> N;
    vector<int> P(N);
    for (auto &&p : P) cin >> p;
    vector<int> D(N, INF);

    // j < i かつ P[j] < P[i] なる j について計算
    calc(N, P, D);

    // j < i かつ P[j] > P[i]
    for (auto &&p : P) p = N + 1 - p;
    calc(N, P, D);

    // j > i かつ P[j] > P[i]
    reverse(begin(P), end(P));
    reverse(begin(D), end(D));
    calc(N, P, D);

    // j > i かつ P[j] < P[i]
    for (auto &&p : P) p = N + 1 - p;
    calc(N, P, D);

    // 反転を直して出力
    reverse(begin(P), end(P));
    reverse(begin(D), end(D));
    for (int i = 0; i < N; ++i) cout << D[i] << " ";
    cout << endl;

    return 0;
}