← 返回题目列表

AtCoder · awc0068_b

B. 农场分区

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

分数: 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