分数: 525 点
问题陈述
AtCoder Inc. 的在线商店目前处理 N 产品,以及产品库存 剩余 i is A_i 单位。
处理以下内容 Q 订单按顺序。的 i第订单如下:
- 购买 k_i 单位每个产品 l_i,l_i+1,\dots,r_i。对于少于以下的产品 k_i 单位,购买所有可用单位。报告在此订单中购买的产品总数。
请注意,对于 i<Q,购买的产品库存 i在继续之前减少第一个订单 (i+1)第一个订单。
约束
- 所有输入值均为整数。
- 1 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^{15}
- 1 \le Q \le 3 \times 10^5
- 1 \le l_i \le r_i \le N
- 1 \le k_i \le 10^9
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N Q l_1 r_1 k_1 l_2 r_2 k_2 \vdots l_Q r_Q k_Q
输出
输出 Q 行。
的 i第行应包含在 i第一个订单。
样本输入 1
6 2 6 4 5 7 5 5 1 6 1 3 5 4 4 4 1 2 5 1 1 6 100
示例输出 1
6 11 0 2 10
该输入包含 5 订单。
- 最初,产品的库存为(来自产品 1 开始) 2,6,4,5,7,5 单位。
- 第一个订单是 l_1 = 1, r_1 = 6, k_1 = 1.
- 按此顺序, 购买了 1,1,1,1,1,1 单位的产品,总计 6 单位。
- 此后,产品库存变为 1,5,3,4,6,4 单位。
- 第二个订单是 l_2 = 3, r_2 = 5, k_2 = 4.
- 按此顺序, 购买了 0,0,3,4,4,0 单位的产品,总计 11 单位。
- 此后,产品库存变为 1,5,0,0,2,4 单位。
- 第三个订单是 l_3 = 4, r_3 = 4, k_3 = 1.
- 按此顺序, 购买了 0,0,0,0,0,0 单位的产品,总计 0 单位。
- 此后,产品库存变为 1,5,0,0,2,4 单位。
- 第四个顺序是 l_4 = 2, r_4 = 5, k_4 = 1.
- 按此顺序, 购买了 0,1,0,0,1,0 单位的产品,总计 2 单位。
- 此后,产品库存变为 1,4,0,0,1,4 单位。
- 第五个订单是 l_5 = 1, r_5 = 6, k_5 = 100.
- 按此顺序, 购买了 1,4,0,0,1,4 单位的产品,总计 10 单位。
- 此后,产品库存变为 0,0,0,0,0,0 单位。