SP13362 KMEDIAL - Median of sub-sequences

我们将一个正整数序列 $S$（长度为 $n$）称为 $x$-中位序列（其中 $x$ 是一个正整数），当且仅当满足以下条件之一： 1. 如果 $n$ 是奇数，$S$ 的中位数（即第 $\left(\frac{n+1}{2}\right)$ 大的元素）等于 $x$；**或者** 2. 如果 $n$ 是偶数，序列中间的两个元素（即第 $\frac{n}{2}$ 大和第 $\left(\frac{n}{2}+1\right)$ 大的元素）都等于 $x$。 现给定一个正整数序列 $A$，长度为 $N$，以及一个正整数 $k$，请找出其中有多少个子序列满足是 $k$-中位序列。 这里，序列 $A$ 的子序列可以表示为 $\{A[i], A[i+1], A[i+2], \ldots, A[j]\}$，其中 $0 \le i \le j < N$。

第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包括两行。第一行有两个整数 $N$ 和 $k$，分别代表序列的长度和目标中位数。 第二行包含 $N$ 个正整数，描述了序列 $A$ 的每个元素。

对于每个测试用例，输出一行，一个整数，表示 $k$-中位序列的子序列数量。

- $1 \le T \le 10^5$，即最多 100,000 个测试用例。 - $1 \le N \le 10^5$，即每个序列的长度不超过 100,000。 - $1 \le k \le 10^9$，即中位数 $k$ 的取值可以很大。 - $1 \le A[i] \le 10^9$，即序列中元素的大小可以较大。 **本翻译由 AI 自动生成**