A16575. Unique Median
编程题
提高+/省选-
知识点
题目描述
如果一个长度为 $m$ 的整数数组 $b$ 满足：将其排序后，有 $b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$，则称其为“好”数组。换句话说，$b$ 是“好”数组当且仅当它的两个中位数相等。特别地，当 $m$ 为奇数时，$\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$，因此长度为奇数的数组一定是“好”数组。
给定一个长度为 $n$ 的整数数组 $a$，请计算 $a$ 中“好”子数组的数量。
$^*$ 数组 $x$ 是数组 $y$ 的子数组，若 $x$ 可以通过从 $y$ 的开头删除若干（可能为零或全部）元素，并从末尾删除若干（可能为零或全部）元素得到。
给定一个长度为 $n$ 的整数数组 $a$，请计算 $a$ 中“好”子数组的数量。
$^*$ 数组 $x$ 是数组 $y$ 的子数组，若 $x$ 可以通过从 $y$ 的开头删除若干（可能为零或全部）元素，并从末尾删除若干（可能为零或全部）元素得到。
输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。
每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10$），表示给定的数组。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10$），表示给定的数组。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每组测试用例，输出一个整数，表示数组 $a$ 中“好”子数组的数量。
输入输出样例
输入 #1
3 4 1 1 1 1 5 1 10 2 3 3 10 6 3 2 3 5 3 4 2 3 5
输出 #1
10 11 42
说明/提示
在第一个样例中，每个子数组都是“好”数组，因为所有元素都等于 $1$。
在第二个样例中，$b = [10, 2, 3, 3]$ 是一个“好”子数组。排序后 $b = [2, 3, 3, 10]$，有 $b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$。另一个例子是 $b = [1, 10, 2]$。而 $b = [1, 10]$ 不是“好”数组，因为它的两个中位数分别是 $1$ 和 $10$，不相等。
在第二个样例中，$b = [10, 2, 3, 3]$ 是一个“好”子数组。排序后 $b = [2, 3, 3, 10]$，有 $b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$。另一个例子是 $b = [1, 10, 2]$。而 $b = [1, 10]$ 不是“好”数组，因为它的两个中位数分别是 $1$ 和 $10$，不相等。