佩蒂亚有一个阵列和 n 个整数。他最近学会了区间和,现在他可以非常快速地计算数组任何区间的元素总和。 现在,他想知道他的数组中总和小于 t 的区间数量是多少?
更确切地说,你需要计算满足 al+al−1+……+ar−1+ar<t 的数对 (l,r) 的数量
第一行包含两个整数 n 和 t ( 1≤n≤200000,∣t∣≤2⋅1014 ).
第二行包含一个整数序列 a1 到 an (∣ai∣≤109),一对 Petya 数组的描述。请注意,可能存在负元素、零元素和正元素。
Petya 数组中的段数,元素之和小于 t.
5 4
5 -1 3 4 -1
5
3 0
-1 2 -3
4
4 -1
-2 1 -2 3
3