AT_abc255_d [ABC255D] ±1 Operation 2

题目描述

给定一个长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$。对 $A$ 进行如下操作称为一次“操作”：

• 首先，选择一个满足 $1 \le i \le N$ 的整数 $i$。
• 然后，从以下两种操作中任选一种执行：
  • 将 $A_i$ 加 $1$。
  • 将 $A_i$ 减 $1$。

请回答 $Q$ 个询问。
第 $i$ 个询问如下：

• 通过任意次数（包括 $0$ 次）的“操作”，将 $A$ 的所有元素都变为 $X_i$ 时，所需的最小“操作”次数是多少？

输入格式

输入以如下格式从标准输入读入。

$N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出格式

请输出 $Q$ 行。
第 $i$ 行输出第 $i$ 个询问的答案，输出为一个整数。

输入输出样例 #1

输入 #1

5 3
6 11 2 5 5
5
20
0

输出 #1

10
71
29

输入输出样例 #2

输入 #2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

输出 #2

3316905982
2811735560
5542639502
4275864946
4457360498

说明/提示

限制条件

• 所有输入均为整数。
• $1 \le N, Q \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $0 \le X_i \le 10^9$

样例解释 1

$A=(6,11,2,5,5)$，该输入包含 $3$ 个询问。对于第 $1$ 个询问，可以通过如下 $10$ 次“操作”将 $A$ 的所有元素变为 $5$：

• $A_1$ 减 $1$ 一次。
• $A_2$ 减 $1$ 共 $6$ 次。
• $A_3$ 加 $1$ 共 $3$ 次。 无法通过 $9$ 次或更少的“操作”完成目标。

对于第 $2$ 个询问，可以通过 $71$ 次“操作”将 $A$ 的所有元素变为 $20$。

对于第 $3$ 个询问，可以通过 $29$ 次“操作”将 $A$ 的所有元素变为 $0$。

样例解释 2

输出结果可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译