[ARC169B] Subsegments with Small Sums

### 题目描述 给定一个正整数 $S$。对于正整数序列 $x$ ，我们定义函数 $f(x)$ 如下: - 将 $x$ 分解为几个连续的子序列。对于每个连续子序列，其元素之和最多为 $S$。$f(x)$ 是在这样的要求下分解成的连续子序列的最小数目。 现在给定一个长度为 $N$ 的正整数序列 $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))$。 ### 输入格式 第一行两个整数 $N$ 和 $S$。 第二行 $N$ 个整数表示序列 $A$。 ### 输出格式 一行一个整数 $\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)$，所有输入都是整数。 样例一解释： 样例中 $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$。

[problemUrl]: https://atcoder.jp/contests/arc169/tasks/arc169_b 正整数 $ 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)) $ の値を求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ S $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

3 3
1 2 3

8

5 1
1 1 1 1 1

35

5 15
5 4 3 2 1

15

20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

588

### 制約 - $ 1\ \leq\ N\ \leq\ 250000 $ - $ 1\ \leq\ S\ \leq\ 10^{15} $ - $ 1\ \leq\ A_i\ \leq\ \min(S,10^9) $ - 入力される値はすべて整数． ### Sample Explanation 1 例えば $ x=(1,2,3) $ を考えると，$ (1,2),(3) $ という分解が条件を満たし， かつ $ 2 $ 個未満の連続部分列に分解した場合は条件を満たさないため，$ 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 $ になります．