配点 : 800 点
問題文
定义 您正在设计将于四月开放的游乐园“Pakenland”。该游乐园的特点是东西狭长,入口位于公园的最西端。下面,入口东侧 k 前进的点 我们称之为 k 。
这个游乐园有景点。 N 基地是的, 它的编号为 1, 2, \dots, N 。景点 i 是一个点 它位于 i 。
定义 您正在邀请企鹅参加 Parkenland 的开幕日。企鹅君 1米继续前进 这将需要 1 秒。企鹅君 M 我已经计划多次乘坐该景点,i 下一站是一个景点 A_i 我已经决定了。 在这个计划中,重点是 A_i 点 移动到 A_{i+1} 所需的最短时间 T_i 秒,移动 这将需要 \sum_{i=1}^{M-1}{T_i} 秒。
现在,就在开幕之前,定义你开始思考,“如果景点排成一排,移动不是很困难吗?”如果再这样下去,企鹅可能会厌倦中途移动并回家。 所以我没有时间 1 我决定只为书籍创建一条扭曲路径。重点 2 如果您选择一个并创建扭曲路径, 2 点之间双向 您可以在 1 秒内移动。 给出
Q 查询。 第i 个查询是“Point S_i 和点 T_i 如果企鹅建造一条连接它们的曲速路,他的计划需要多少秒才能完成?请回答每个问题。
制約
- 2 \leq N, M \leq 300000
- 1 \leq Q \leq 300000
- 1 \leq A_i \leq N (1 \leq i \leq M)
- A_i \neq A_{i+1} (1 \leq i \leq M-1)
- 1 \leq S_i < T_i \leq N (1 \leq i \leq Q)
小課題
- (20 点) M, Q \leq 5000
- (50 点) N \leq 300, |A_i - A_{i+1}| \leq 10 (1 \leq i \leq M-1)
- (100 点) N \leq 300
- (280 点) N \leq 2000
- (300 点) M, Q \leq 50000
- (50 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。所有输入均为整数。 请输出
N\ M A_1\ A_2\ \dots\ A_M Q S_1\ T_1 \vdots S_Q\ T_Q
出力
到标准输出 输出 Q 行。i 行是查询 请打印答案 i 。
入力例 1
5 6 3 5 2 1 5 3 2 1 3 2 5
出力例 1
11 8
查询 2 例如,企鹅的动作如下。 转到
- 地点 3 点 移动到 2 (1 秒)
- 使用扭曲的点 2 点 移动到 5 (1 秒)
- 使用扭曲的点 5 点 移动到 2 (1 秒)
- 地点 2 点 移动到 1 (1 秒)
- 地点 1 点 移动到 2 (1 秒)
- 使用扭曲的点 2 点 移动到 5 (1 秒)
- 地点 5 点 移动到 3 (2 秒)
请注意,企鹅总是在尽可能短的时间内移动。此示例输入满足所有子任务约束。
入力例 2
10 10 3 1 4 1 2 9 3 2 7 10 10 1 7 1 4 3 8 6 9 3 4 1 8 7 10 4 10 3 5 6 9
出力例 2
24 27 21 27 31 23 29 25 28 27
此输入示例满足所有子任务约束。
入力例 3
100 20 6 97 94 50 96 51 94 86 92 77 9 73 21 9 46 42 76 77 49 17 20 38 87 20 60 5 56 8 82 69 80 13 42 90 99 97 98 96 97 95 97 61 88 48 61 11 73 42 81 8 18 78 83 17 54 41 68 2 69 72 100
出力例 3
401 451 449 417 573 489 625 633 633 631 493 535 401 393 596 609 451 467 437 543
此输入示例满足子任务 1、3、4、5、6 的约束。
原案: 定义