← 返回题目列表

AtCoder · pakencamp_2021_day3_f

F. 扭曲

中文机器翻译题面 查看原题

配点 : 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)

小課題

  1. (20 点) M, Q \leq 5000
  2. (50 点) N \leq 300, |A_i - A_{i+1}| \leq 10 (1 \leq i \leq M-1)
  3. (100 点) N \leq 300
  4. (280 点) N \leq 2000
  5. (300 点) M, Q \leq 50000
  6. (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 例如,企鹅的动作如下。 转到

  1. 地点 3 点 移动到 2 (1 秒)
  2. 使用扭曲的点 2 点 移动到 5 (1 秒)
  3. 使用扭曲的点 5 点 移动到 2 (1 秒)
  4. 地点 2 点 移动到 1 (1 秒)
  5. 地点 1 点 移动到 2 (1 秒)
  6. 使用扭曲的点 2 点 移动到 5 (1 秒)
  7. 地点 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 的约束。

原案: 定义