分数: 300 分
问题陈述
高桥管理着一个巨大的农场。农场有 N 字段从东到西排列成一排,每个字段编号从 1 to N 按从西到东的顺序。田间收获产量 i (1 \leq i \leq N) is A_i.
为了提高农场管理效率,高桥决定将这些田地划分为 M 部分。每个部分由连续编号的字段组成。具体来说, j第节 (1 \leq j \leq M) 由字段中的连续字段组成 L_j 到现场 R_j (L_j \leq R_j)。每个字段都属于一个节,节之间不共享任何字段。请注意,输入中的各部分不一定按从西到东的顺序给出。
的 生产力 每个部分的 被定义为该部分中包含的所有田地的收获产量的总和。也就是说,生产力 j第节是 A_{L_j} + A_{L_j+1} + \cdots + A_{R_j}.
Takahashi 希望了解各部门之间生产率的差异。这是因为,如果生产率差异太大,就很难分配工人和分配资源。
对于给定的分区,找出从最大生产率减去最小生产率得到的值 M 部分。
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
- 的 M 节分区字段 1 通过 N 完全没有重叠或遗漏
- 输入中的部分不一定按从西到东的顺序给出
- 所有输入值均为整数
输入
N M A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_M R_M
- 第一行包含字段数 N 和节数 M,用空格分隔。
- 第二行包含收获产量 每个字段的 A_1, A_2, \ldots, A_N ,以空格分隔。
- 以下 M 行描述了每个部分的组成。
- 的 (2 + j)第行 (1 \leq j \leq M) 包含字段编号的范围 L_j 和 R_j 组成 j第一部分,以空格分隔。该部分由 field 中的字段组成 L_j 到现场 R_j.
输出
在一行中输出从最大生产率中减去最小生产率所得的值 M 部分。
示例输入 1
5 3 10 20 30 40 50 1 2 3 3 4 5
示例输出 1
60
示例输入 2
8 4 5 15 10 20 25 5 30 10 1 3 4 4 5 6 7 8
示例输出 2
20
示例输入 3
12 5 100 200 300 150 250 50 400 100 200 300 150 100 1 2 3 5 6 8 9 10 11 12
示例输出 3
450