CF1042D Petya and Array

Petya 有一个包含 $n$ 个整数的数组 $a$。他最近学会了前缀和，现在可以非常快速地计算数组中任意一段连续区间的元素和。区间指的是数组中一段连续的非空元素序列。 现在他想知道，数组中有多少个区间的元素和小于 $t$。请你帮助 Petya 计算这个数量。 更正式地说，你需要计算有多少对 $l, r$（$l \le r$）满足 $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$。

第一行包含两个整数 $n$ 和 $t$（$1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_{i}| \le 10^{9}$）——这是 Petya 的数组。注意，数组中的元素可以为负数、零或正数。

输出 Petya 的数组中，元素和小于 $t$ 的区间数量。

在第一个样例中，以下区间的元素和小于 $4$： - $[2, 2]$，元素和为 $-1$ - $[2, 3]$，元素和为 $2$ - $[3, 3]$，元素和为 $3$ - $[4, 5]$，元素和为 $3$ - $[5, 5]$，元素和为 $-1$。 由 ChatGPT 4.1 翻译