← 返回题目列表

AtCoder · abc426_f

I. 间隙

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

分数: 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 单位。