#78. 优美树列
优美树列
题目背景
中位数(median)是将一组数据按照从小到大的顺序排列(或者从大到小的顺序也可以)之后处在数列中点位置的数值,是典型的位置平均数,不受极端变量值的影响。中位数主要用于顺序数据,也可用数值型数据,但不能用于分类数据。
如果排好序的数列元素个数 n 是奇数,中位数等于第 (n+1)/2 个数;如果元素个数 n 是偶数,中位数等于第 n/2 和第 n/2 + 1个数的平均数。对于一组数据来说,中位数是唯一的。比如,有一组数据是:1,2,5,9,11,还有一组数据是1,2,5,9,11,12。他们分别的中位数如下示意图所示。

其中第一组数据的中位数是 5,第二组数据的中位数为 (5+9)/2=7。
题目描述
植树节那天,沿着马路一侧,同学们种了 n 棵树。
现在想要评估一下这些树种植得是否优美。
首先,信竞队长自左向右将这些树编号为 1 ~ n。然后根据种植情况给每棵树打了一个分数,编号为 i 的树的得分为 Ai。
然后,队长给出了一个评估值 P。对于任意一段位置连续的树,定义这个树段的美观度为这个段所包含的树的欣赏度的中位数,记为 M,如果 M ≥ P,则称这个树段为一个“优美树列”。
问:“优美树列”有多少个?
注意:本题中当 n 为偶数时,定义中位数为第 n/2 和第 n/2 + 1 个数的较大的那个,而非取二者的平均数。
输入格式
第一行:两个整数 n, P
接下来 n 行:每行一个整数 Ai
输出格式
一个整数,表示“优美树列”的个数
样例输入
5 6
8
1
2
6
2
样例输出
6
样例解释
长度为 1:{8}, {6}
长度为 2:{8, 1}, {2, 6}, {6, 2}
长度为 3:无
长度为 4:{8, 1, 2, 6}
长度为 5:无
数据范围
20% 的数据:n ≤ 100
30% 的数据:n ≤ 10^3
40% 的数据:n ≤ 10^4
80% 的数据:1 ≤ n ≤ 10^5
90% 的数据:1 ≤ n ≤ 10^7
100% 的数据:1 ≤ n ≤ 2×10^7, 1 ≤ Ai, P ≤ 10^9