CF1005E2.Median on Segments (General Case Edition)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given an integer sequence $a_1, a_2, \dots, a_n$ .

Find the number of pairs of indices $(l, r)$ ( $1 \le l \le r \le n$ ) such that the value of median of $a_l, a_{l+1}, \dots, a_r$ is exactly the given number $m$ .

The median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.

For example, if $a=[4, 2, 7, 5]$ then its median is $4$ since after sorting the sequence, it will look like $[2, 4, 5, 7]$ and the left of two middle elements is equal to $4$ . The median of $[7, 1, 2, 9, 6]$ equals $6$ since after sorting, the value $6$ will be in the middle of the sequence.

Write a program to find the number of pairs of indices $(l, r)$ ( $1 \le l \le r \le n$ ) such that the value of median of $a_l, a_{l+1}, \dots, a_r$ is exactly the given number $m$ .

输入格式

The first line contains integers $n$ and $m$ ( $1 \le n,m \le 2\cdot10^5$ ) — the length of the given sequence and the required value of the median.

The second line contains an integer sequence $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 2\cdot10^5$ ).

输出格式

Print the required number.

输入输出样例

输入#1
```
5 4
1 4 5 60 4
```
输出#1
```
8
```
输入#2
```
3 1
1 1 1
```
输出#2
```
6
```
输入#3
```
15 2
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
```
输出#3
```
97
```

说明/提示

In the first example, the suitable pairs of indices are: $(1, 3)$ , $(1, 4)$ , $(1, 5)$ , $(2, 2)$ , $(2, 3)$ , $(2, 5)$ , $(4, 5)$ and $(5, 5)$ .

首页