题解 | 小红统计区间（hard）

'''
暴力解法，运算之间过长，需要计算n^2
n, k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(len(a)):
    for j in range(i,len(a)):
        sub_list = a[i:j+1]
        result = sum(sub_list)
        if result >=k:
            count += 1
print(count)
'''
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))

prefix_sums = [0]#存放累计求和
current_sum = 0
count = 0
for num in a: 运算n次
    current_sum += num
    target = current_sum - k 
    cnt = bisect.bisect_right(prefix_sums, target) # 找到有多少个前缀和小于等于target 更快的比较方法 logn
    count += cnt
    bisect.insort(prefix_sums, current_sum) #插入新的求和信息
print(count)
#思路 对于累计求和大于等于 target  可以转换为当前求和 - 历史求和 大于等于 target 最开始的求和结果是0。
#然后当前求和 - 历史求和 >= target --> 当前求和 - target >= 历史求和 如果我们能得到求和信息，就可以用二分法查找
# 例：n =5 k =2 [2,1,-1,-2,4] 求和序列 [0,2,3,2,0,4] 注意这个是有顺序的，新求和只能插入到最后
对于2-0>=2 ;3-0>=2 ;2-0>=2 ;4-0>=2 4-2>=2 4-2>=2 4-0>=2 共7种