CF1234E Special Permutations

我们定义 $p_i(n)$ 为如下排列：$[i, 1, 2, \dots, i - 1, i + 1, \dots, n]$。也就是说，第 $i$ 个排列几乎是一个恒等排列（即每个元素都映射到自身），但元素 $i$ 被放在了第一个位置。例如： - $p_1(4) = [1, 2, 3, 4]$； - $p_2(4) = [2, 1, 3, 4]$； - $p_3(4) = [3, 1, 2, 4]$； - $p_4(4) = [4, 1, 2, 3]$。 给定一个数组 $x_1, x_2, \dots, x_m$（$1 \le x_i \le n$）。 记 $pos(p, val)$ 表示元素 $val$ 在排列 $p$ 中的位置。例如，$pos(p_1(4), 3) = 3$，$pos(p_2(4), 2) = 1$，$pos(p_4(4), 4) = 1$。 定义函数 $f(p) = \sum\limits_{i=1}^{m - 1} |pos(p, x_i) - pos(p, x_{i + 1})|$，其中 $|val|$ 表示 $val$ 的绝对值。该函数表示在排列 $p$ 中，数组 $x$ 的相邻元素之间的位置距离之和。 你的任务是计算 $f(p_1(n)), f(p_2(n)), \dots, f(p_n(n))$。

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$），分别表示每个排列中的元素个数和数组 $x$ 的元素个数。 第二行包含 $m$ 个整数（注意是 $m$ 个，不是 $n$ 个）$x_1, x_2, \dots, x_m$，其中 $x_i$ 是数组 $x$ 的第 $i$ 个元素。$x$ 中的元素可以重复，顺序任意。

输出 $n$ 个整数，依次为 $f(p_1(n)), f(p_2(n)), \dots, f(p_n(n))$。

考虑第一个样例： $x = [1, 2, 3, 4]$，因此 - 对于排列 $p_1(4) = [1, 2, 3, 4]$，答案为 $|1 - 2| + |2 - 3| + |3 - 4| = 3$； - 对于排列 $p_2(4) = [2, 1, 3, 4]$，答案为 $|2 - 1| + |1 - 3| + |3 - 4| = 4$； - 对于排列 $p_3(4) = [3, 1, 2, 4]$，答案为 $|2 - 3| + |3 - 1| + |1 - 4| = 6$； - 对于排列 $p_4(4) = [4, 1, 2, 3]$，答案为 $|2 - 3| + |3 - 4| + |4 - 1| = 5$。 再看第二个样例： $x = [2, 1, 5, 3, 5]$，因此 - 对于排列 $p_1(5) = [1, 2, 3, 4, 5]$，答案为 $|2 - 1| + |1 - 5| + |5 - 3| + |3 - 5| = 9$； - 对于排列 $p_2(5) = [2, 1, 3, 4, 5]$，答案为 $|1 - 2| + |2 - 5| + |5 - 3| + |3 - 5| = 8$； - 对于排列 $p_3(5) = [3, 1, 2, 4, 5]$，答案为 $|3 - 2| + |2 - 5| + |5 - 1| + |1 - 5| = 12$； - 对于排列 $p_4(5) = [4, 1, 2, 3, 5]$，答案为 $|3 - 2| + |2 - 5| + |5 - 4| + |4 - 5| = 6$； - 对于排列 $p_5(5) = [5, 1, 2, 3, 4]$，答案为 $|3 - 2| + |2 - 1| + |1 - 4| + |4 - 1| = 8$。 由 ChatGPT 4.1 翻译