#ABC130D. 足够的数组

足够的数组

AT_abc130_d [ABC130D] Enough Array

题目描述

\hspace{15pt}给定一个长度为 nn 的正整数序列 a1,a2,…,ana_1,a_2,\dots,a_n 和一个整数 kk。请你求出有多少个满足以下条件的连续子数组:

∙ \hspace{23pt}\bullet\,该连续子数组中所有元素的和不小于 kk。

\hspace{15pt}注意,即使两个连续子数组的内容相同,只要它们在序列中的位置不同,也要分别计数。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\, 子数组:子数组为从原数组中,连续的选择一段元素(可以全选、可以不选)得到的新数组。

输入格式

\hspace{15pt}第一行输入两个整数 $n,k \left(1 \leqq n \leqq 10^5;\ 1 \leqq k \leqq 10^{10}\right)$ 代表序列的长度和阈值。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^5\right)$ 代表序列中的元素。

输出格式

\hspace{15pt}在一行上输出一个整数,代表满足条件的连续子数组数量。

\hspace{15pt}请注意,答案可能超出 3232 位整数范围。

测试样例

4 10
6 1 2 7
2

样例 1 解释

\hspace{15pt}在这个样例中,满足条件的连续子数组有:

∙ \hspace{23pt}\bullet\, a1,a2,a3,a4a_1,a_2,a_3,a_4,元素和为 6+1+2+7=166+1+2+7=16;

∙ \hspace{23pt}\bullet\, a2,a3,a4a_2,a_3,a_4,元素和为 1+2+7=101+2+7=10。

\hspace{15pt}共 22 种,因此输出 22。

3 5
3 3 3
3

样例 2 解释

\hspace{15pt}在这个样例中,满足条件的连续子数组为 a1,a2a_1,a_2、a2,a3a_2,a_3 与 a1,a2,a3a_1,a_2,a_3,共 33 种。

\hspace{15pt}其中 a1,a2a_1,a_2 与 a2,a3a_2,a_3 的内容相同,但它们的位置不同,需要分别计数。

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352
36