P12570 [UOI 2023] An Array and Medians of Subarrays

对于一个长度为 $(2 \cdot k + 1)$ 的数组，我们将其元素按非递减顺序排序后，第 $(k + 1)$ 位的数字称为该数组的**中位数**。例如，数组 $[1]$、$[4,2,5]$ 和 $[6,5,1,2,3]$ 的中位数分别是 $1$、$4$ 和 $3$。 给定一个长度为**偶数** $n$ 的整数数组 $a$。 判断是否可以将 $a$ 分割成若干个长度为**奇数**的子数组，使得所有这些子数组的中位数都相等。 形式化地说，你需要判断是否存在一个整数序列 $i_1, i_2, \ldots, i_k$，满足以下条件： - $1 = i_1 < i_2 < \ldots < i_k = (n + 1)$； - $(i_2 - i_1) \bmod 2 = (i_3 - i_2) \bmod 2 = \ldots = (i_k - i_{k - 1}) \bmod 2 = 1$； - $f(a[i_1..(i_2-1)]) = f(a[i_2..(i_3-1)]) = \ldots = f(a[i_{k - 1}..(i_k - 1)])$，其中 $a[l..r]$ 表示由元素 $a_l, a_{l + 1}, \ldots, a_r$ 组成的子数组，$f(a)$ 表示数组 $a$ 的中位数。

第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）——数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。 保证 $n$ 是偶数。

如果可以将 $a$ 分割成若干个长度为奇数的子数组，且这些子数组的中位数都相等，则输出 `Yes`，否则输出 `No`。

在第一个样例中，数组 $[1,1,1,1]$ 可以分割为 $[1]$ 和 $[1,1,1]$，它们的中位数均为 $1$。 在第二个样例中，数组 $[1,2,3,3,2,1]$ 可以分割为 $[1,2,3]$ 和 $[3,2,1]$，它们的中位数均为 $2$。 在第三个样例中，数组 $[1,2,1,3,2,3]$ 无法被分割为若干个长度为奇数的子数组，且这些子数组的中位数相等。 ### 评分标准 - （$3$ 分）：$n=2$； - （$14$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 2$； - （$12$ 分）：对于 $1 \le i < n$，$a_i \le a_{i+1}$； - （$16$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 3$，且每个值在 $a$ 中出现的次数不超过 $\frac{n}{2}$； - （$17$ 分）：$n \le 100$； - （$18$ 分）：$n \le 2000$； - （$20$ 分）：无额外限制。 翻译由 DeepSeek V3 完成