分数: 500 点
问题陈述
给你一个正整数 S。 对于正整数序列 x,我们定义 f(x) 如下:
- 考虑分解 x 分成几个连续的子序列。对于每个连续子序列,其元素之和必须为 最多 S。 这种分解中连续子序列的最小数量是 f(x).
可以证明 的值 f 在此问题的约束下始终是可定义的。
给你一个正整数序列 A=(A_1,A_2,\cdots,A_N)。 求出 的值 \sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r)).
约束
- 1 \leq N \leq 250000
- 1 \leq S \leq 10^{15}
- 1 \leq A_i \leq \min(S,10^9)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N S A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
3 3 1 2 3
示例输出 1
8
例如,考虑 x=(1,2,3)。分解 (1,2),(3) 满足条件,并且分解为少于两个连续子序列满足条件,所以 f((1,2,3))=2.
下面显示的是可能的 l,r 以及相应的值 f:
- (l,r)=(1,1): f((1))=1
- (l,r)=(1,2): f((1,2))=1
- (l,r)=(1,3): f((1,2,3))=2
- (l,r)=(2,2): f((2))=1
- (l,r)=(2,3): f((2,3))=2
- (l,r)=(3,3): f((3))=1
因此,答案是 1+1+2+1+2+1=8.
示例输入 2
5 1 1 1 1 1 1
示例输出 2
35
示例输入 3
5 15 5 4 3 2 1
示例输出 3
15
示例输入 4
20 1625597454 786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130
示例输出 4
588