平面走査の問題で，実装ではsegtreeを使う．
まず，絶対値を外して考えるために，4つに場合分けする． 実装では，reverse をしたりすればある程度使いまわせるので，4つ書く必要はない．
Case: \(i > j \) かつ \(P_{i} > P_{j}\)
これは，よくある平面走査の形． ソートされているので， \(i\) に関してループを回しているとき， ループが終わった部分 \(j\) については， \(i > j\) が保証されている． 逆に，その様な \(j\) が全て計算ずみでもある． あとは segtree で \(a_{i}\) の値を記録すれば，minを \(O(log N)\) で求められる．
実装
reverse するときに，答えを入れる配列も一緒に reverse するのを忘れないこと． また，segtree の vertex (あるいは定義域)は \(a_{i}\) であって， \(i\) ではない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll op(ll a, ll b){
return min(a,b);
}
ll e(){
return INFL;
}
int main() {
ll n, m ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; --a[i]; }
vll ans(n, INFL);
rep(_,2){
segtree<ll, op, e> st(n), st1(n);
rep(i,n){
chmin(ans[i], st.prod(0, a[i]) + (i+a[i]));
chmin(ans[i], st1.prod(a[i]+1, n) + (i-a[i]));
st.set(a[i], -(i+a[i]));
st1.set(a[i], -i+a[i]);
}
reverse(all(a));
reverse(all(ans)); // not forget
}
rep(i,n){
cout << ans[i] << " ";
}
return 0;
}
