分数: 333 分
问题陈述
高桥担任大型工厂参观导游。
工厂有 N 制造区域,每个编号从 1 to N。参观各个区域 i 正好需要 T_i 分钟。
今天, M 旅游团将参观工厂。各组 j 到达工厂时间 S_j 分钟,到达后立即访问所有号码为 L_j to R_j。团队按照区域编号递增的顺序逐一参观,参观完一个区域后立即开始参观下一个区域(区域之间没有行进时间)。
每个区域都足够宽敞,即使多个团体同时访问同一区域,也不会互相影响。
高桥想提前计算出每个小组完成所有访问的时间,并通知各小组。
对于每个小组,确定他们完成访问所有指定区域的时间(以分钟为单位)。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq S_j \leq 10^9
- 1 \leq L_j \leq R_j \leq N
- 所有输入值均为整数。
输入
N M T_1 T_2 \ldots T_N S_1 L_1 R_1 S_2 L_2 R_2 \vdots S_M L_M R_M
- 第一行包含区域数 N 和组数 M,用空格分隔。
- 第二行包含访问次数 每个区域的 T_1, T_2, \ldots, T_N ,用空格分隔。
- 以下 M 行包含每个组的信息。
- 的 树的 (2 + j)第行包含到达时间 S_j 的 j第组,开始 L_j 并结束 R_j 要访问的区域号码范围,以空格分隔。
输出
打印 M 行。
的 树的 j- 第行应包含时间(以分钟为单位) j第一组完成所有访问。
示例输入 1
5 3 10 20 30 40 50 0 1 3 5 2 4 100 5 5
示例输出 1
60 95 150
示例输入 2
4 5 15 25 10 30 0 1 4 10 1 1 20 2 3 0 3 4 50 1 2
示例输出 2
80 25 55 40 90
示例输入 3
10 6 100 200 300 150 250 50 400 100 350 200 0 1 10 1000 3 7 500 1 5 0 6 10 200 4 6 999999999 1 1
示例输出 3
2100 2150 1500 1100 650 1000000099