102835: [Atcoder]ABC283 F - Permutation Distance
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
Problem Statement
You are given a permutation $P=(P _ 1,P _ 2,\ldots,P _ N)$ of $(1,2,\ldots,N)$.
Find the following value for all $i\ (1\leq i\leq N)$:
- $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$.
What is a permutation?
A permutation of $(1,2,\ldots,N)$ is a sequence that is obtained by rearranging $(1,2,\ldots,N)$. In other words, a sequence $A$ of length $N$ is a permutation of $(1,2,\ldots,N)$ if and only if each $i\ (1\leq i\leq N)$ occurs in $A$ exactly once.Constraints
- $2 \leq N \leq 2\times10^5$
- $1 \leq P _ i \leq N\ (1\leq i\leq N)$
- $i\neq j\implies P _ i\neq P _ j$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $P _ 1$ $P _ 2$ $\ldots$ $P _ N$
Output
Print $D _ i\ (1\leq i\leq N)$ in ascending order of $i$, separated by spaces.
Sample Input 1
4 3 2 4 1
Sample Output 1
2 2 3 3
For example, for $i=1$,
- if $j=2$, we have $\left\lvert P _ i-P _ j\right\rvert=1$ and $\left\lvert i-j\right\rvert=1$;
- if $j=3$, we have $\left\lvert P _ i-P _ j\right\rvert=1$ and $\left\lvert i-j\right\rvert=2$;
- if $j=4$, we have $\left\lvert P _ i-P _ j\right\rvert=2$ and $\left\lvert i-j\right\rvert=3$.
Thus, the value is minimum when $j=2$, where $\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2$, so $D _ 1=2$.
Sample Input 2
7 1 2 3 4 5 6 7
Sample Output 2
2 2 2 2 2 2 2
Sample Input 3
16 12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9
Sample Output 3
3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7
Input
题意翻译
给定一个 $1 \sim n$ 的排列 $p = (p_1, p_2, \dots, p_n)$。 你需要对每个 $i$ 求得 $$D_i = \min_{j \neq i} \left\{ \lvert p_i - p_j\rvert + \lvert i - j\rvert \right\} $$ 一个 $1\sim n$ 的排列是一个长为 $n$ 的序列，满足 $[1, n]$ 内的所有整数恰好都在其中出现一次。 $2\le n \le 2\times 10^5$。Output
得分：500分
部分
问题描述
给你一个排列 $P=(P _ 1,P _ 2,\ldots,P _ N)$，其中 $(1,2,\ldots,N)$ 的排列。
对于所有的 $i\ (1\leq i\leq N)$，找到以下值：
* $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$。
详情
$(1,2,\ldots,N)$ 的排列是指通过重新排列 $(1,2,\ldots,N)$ 而得到的序列。
换句话说，长度为 $N$ 的序列 $A$ 是 $(1,2,\ldots,N)$ 的排列，当且仅当每个 $i\ (1\leq i\leq N)$ 在 $A$ 中恰好出现一次。
部分
限制条件
* $2 \leq N \leq 2\times10^5$
* $1 \leq P _ i \leq N\ (1\leq i\leq N)$
* $i\neq j\implies P _ i\neq P _ j$
* 输入中的所有值都是整数。
部分
输入
输入格式如下：
$N$
$P _ 1$ $P _ 2$ $\ldots$ $P _ N$
部分
输出
以 $i$ 的升序顺序打印 $D _ i\ (1\leq i\leq N)$，用空格分隔。
部分
样例输入 1
4
3 2 4 1
部分
样例输出 1
2 2 3 3
例如，对于 $i=1$，
* 如果 $j=2$，我们有 $\left\lvert P _ i-P _ j\right\rvert=1$ 和 $\left\lvert i-j\right\rvert=1$；
* 如果 $j=3$，我们有 $\left\lvert P _ i-P _ j\right\rvert=1$ 和 $\left\lvert i-j\right\rvert=2$；
* 如果 $j=4$，我们有 $\left\lvert P _ i-P _ j\right\rvert=2$ 和 $\left\lvert i-j\right\rvert=3$。
因此，当 $j=2$ 时，值最小，其中 $\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2$，因此 $D _ 1=2$。
部分
样例输入 2
7
1 2 3 4 5 6 7
部分
样例输出 2
2 2 2 2 2 2 2
部分
样例输入 3
16
12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9
部分
样例输出 3
3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7