P12644 [KOI 2024 Round 1] 会议地点

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在 KOI 村中，$N$ 户人家建在一条数轴直线上。每户人家住着一位居民。将这些人家的坐标按从小到大的顺序排列，第 $i$ 户人家的坐标为 $X_i$（$X_i > 0$）。 当村子中有事务需要处理时，村民们会通过“会议集合”进行决策。每个会议集合可以由全体村民参与，也可以只由部分人参与。会议集合由若干场会议组成，每场会议都在参与者之一的家中举行。每个参与者的家中都会轮流召开一次会议，因此如果一个会议集合中有 $K$ 位村民参与，那么这个集合中会举行 $K$ 场会议。 每场会议的开销是所有参与者从自己家前往会议地点所需的距离之和。一个会议集合的“疲劳度”由所有会议的开销顺序决定，定义为按照会议顺序，相邻两场会议的开销差的绝对值之和。 例如，若人们住在坐标为 $1$、$3$、$10$、$11$、$15$ 的位置，其中住在 $3$、$10$ 和 $11$ 的三位居民参与会议集合，则： - 在坐标为 $3$ 的家开会的开销为 $|3 - 3| + |3 - 10| + |3 - 11| = 15$； - 在坐标为 $10$ 的家开会的开销为 $|10 - 3| + |10 - 10| + |10 - 11| = 8$； - 在坐标为 $11$ 的家开会的开销为 $|11 - 3| + |11 - 10| + |11 - 11| = 9$。 若会议召开顺序为 $3 \rightarrow 10 \rightarrow 11$，则疲劳度为 $|15 - 8| + |8 - 9| = 8$； 若顺序为 $3 \rightarrow 11 \rightarrow 10$，则疲劳度为 $|15 - 9| + |9 - 8| = 7$，此时疲劳度最小。 如果会议集合中参与者不超过 $1$ 人，疲劳度为 $0$。 KOI 村将举行共 $Q$ 次会议集合。第 $i$ 次会议集合的参与者是住在坐标区间 $[L_i, R_i]$ 内的所有居民。请你编程，求出每次会议集合的最小疲劳度。

第一行输入两个整数 $N$ 和 $Q$，以空格分隔。 第二行输入 $N$ 个整数，表示居民所在的房屋坐标 $X_1, X_2, \dots, X_N$，按升序排列。 接下来的 $Q$ 行，每行输入两个整数 $L_i$ 和 $R_i$，表示第 $i$ 次会议集合的参与者坐标范围。

输出 $Q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次会议集合的最小疲劳度。

**约束条件** - 所有给定数值均为整数。 - $1 \leq N \leq 200\,000$ - $1 \leq Q \leq 200\,000$ - $1 \leq X_i \leq 10^9 \quad (1 \leq i \leq N)$ - $X_i < X_{i+1} \quad (1 \leq i < N)$ - $1 \leq L_i \leq R_i \leq 10^9 \quad (1 \leq i \leq Q)$ **子问题** 1. （5 分）$N \leq 5$，$Q \leq 5$ 2. （15 分）$N \leq 16$，$Q \leq 16$ 3. （15 分）$N \leq 500$，$Q \leq 500$ 4. （30 分）$N \leq 3\,000$，$Q \leq 3\,000$ 5. （35 分）无附加限制条件 翻译由 ChatGPT-4o 完成