分数: 366 分
问题陈述
高桥是一位来访的送货员 N 仓库排列成一排,按顺序收集包裹。仓库都有编号 1, 2, \ldots, N 从西到东,还有仓库 i 包含一包重量 A_i.
高桥从某个仓库开始 s (1 \leq s \leq N)没有携带任何包裹,向东依次访问仓库。每次他访问仓库时,他都会在那里拿起包裹并将其添加到他的货物中。他保留了他收到的所有包裹。
具体来说,在每个仓库,他都遵循以下步骤:
- 在那个仓库拿起包裹并将其添加到他的负载中。
- 检查他的货物总重量(包括刚刚拿起的包裹)。
- 如果总重量大于 K (即超过 K),高桥无法继续前进并停在该仓库。
- 如果总重量最多为 K 且当前仓库不是仓库 N,他移动到下一个仓库(东边的邻近仓库)并返回到步骤 1。
- 如果总重量最多为 K 且当前仓库为仓库 N,东边已经没有仓库了,所以他停在了那个仓库。
也就是说,从仓库出发时 s,高桥参观仓库 s, s+1, s+2, \ldots 有序,并停在仓库 t 其中累计包裹重量 A_s + A_{s+1} + \cdots + A_t 首先超过 K。如果他到达仓库 N 超出无 K,他停在仓库 N.
定义 f(s) 为Takahashi停靠的仓库编号。
高桥想回答 Q 问题。 j第一个问题,整数 给出了表示起始点范围的 L_j, R_j 。求出 的值 f(L_j) + f(L_j + 1) + \cdots + f(R_j).
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq Q \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 Q)
- 所有输入值均为整数。
输入
N K Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含仓库数量 N,总重量上限 K,以及问题数量 Q,用空格分隔。
- 第二行包含每个仓库的包裹重量 A_1, A_2, \ldots, A_N,用空格分隔。
- 以下 Q 行每条都包含起点范围 每个问题的 L_j, R_j ,用空格分隔。
输出
打印 Q 行。上 j第行,打印答案 j第一个问题,即值 f(L_j) + f(L_j + 1) + \cdots + f(R_j).
示例输入 1
5 10 3 3 4 2 5 1 1 5 1 3 3 5
示例输出 1
23 13 15
示例输入 2
4 5 2 3 3 3 3 1 4 2 3
示例输出 2
13 7
示例输入 3
10 15 4 5 3 7 2 8 1 4 6 9 3 1 10 3 7 1 1 5 10
示例输出 3
78 39 4 56
示例输入 4
15 20 5 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 1 15 5 10 1 5 10 15 8 12
示例输出 4
164 62 35 90 67
示例输入 5
1 1000000000000000 1 1 1 1
示例输出 5
1