← 返回题目列表

AtCoder · awc0088_c

C. 农场丰收节

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

分数: 366 分

问题陈述

高桥管理着一个巨大的农场。

农场有 N 连续排列的图,编号为 1 to N。情节 i (1 \leq i \leq N) 里面种植了一棵果树,可以收获的果实数量为 A_i 公斤。

丰收祭期间,高桥表演 M 收获作业。在 j-th (1 \leq j \leq M) 收获操作,他从地块中的所有连续地块中收获水果 L_j 绘制 R_j.

每块地里的果实一旦收获就消失了。因此,即使一块地块包含在多次收获作业中,从该地块获得的产量也只是从第一次开始,即 A_i 公斤。

也就是说,高桥获得的总收获是 A_i 至少有一个目标的所有地块 M 收获作业。求此总收获。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \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)
  • 所有输入均为整数

输入

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 行, j第行 (1 \leq j \leq M) 包含左端点 L_j 和右端点 R_j 所针对的地块范围 j-th 收获操作,以空格分隔。

输出

在一行中输出高桥获得的果实的总收获量。


示例输入 1

5 3
10 20 30 40 50
1 3
2 4
4 5

示例输出 1

150

示例输入 2

7 4
5 12 8 3 15 9 6
1 2
4 6
2 5
1 7

示例输出 2

58

示例输入 3

10 6
100 250 180 90 320 150 200 80 170 260
1 3
5 7
2 4
6 9
1 1
8 10

示例输出 3

1800