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