子串的平均数(Average of Substring)

题目描述

给定一个整数序列 $a_1,a_2,\dots,a_n$，再给定一个整数 $m$，该序列有多少子串（子串就是一段连续的子序列）的平均数大于或等于 $m$？

输入格式

第一行：两个整数表示 $n$ 与 $m$；

第二行：$n$ 个整数表示 $a_1,a_2,\dots,a_n$。

输出格式

单个整数：表示平均数大于或等于 $m$ 的子串数量。

样例输入 #1

3 3
1 2 3

样例输出 #1

1

说明：只有子串 {3} 的平均数达到 3。

样例输入 #2

3 2
1 3 2

样例输出 #2

5

说明：{1,3}、{3}、{3,2}、{2}、{1,3,2} 都满足要求。

数据范围

• $0\le a_i\le 10^9$；
• $0\le m\le 10^9$；
• 对于 $30\%$ 的数据，$1\le n\le 100$；
• 对于 $60\%$ 的数据，$1\le n\le 5000$；
• 对于 $100\%$ 的数据，$1\le n\le 200000$。

知识点与难度

本题涉及的知识点从属于 GESP 七级（归并排序、前缀和、逆序对），难度等级：⭐⭐⭐⭐。

测试点分布