P17143 [NOI 2026] 中位数

题面、样例附件来自 [QOJ](https://qoj.ac/contest/3939/problem/18986)。 提交到洛谷上时，无需引用头文件 `#include "median.h"`。直接将 ```cpp void init(int c, int t); int median(int n, int k, std::vector a); ``` 复制到程序开头，同时选用 C++17 或者更高版本编译器编译。

对于大小为 $m$ 的可重集 $S=\{x_0,x_1,\ldots,x_{m-1}\}$，设其所有元素 **从大到小** 排序后的结果为 $y_0\ge y_1\ge\cdots\ge y_{m-1}$。定义其 **中位数** $\operatorname{Median}(S)$ 为其中第 $\left\lceil\frac{m}{2}\right\rceil$ 大的数，即 $\operatorname{Median}(S)=y_{\left\lceil\frac{m}{2}\right\rceil-1}$。**注意：本题中的中位数定义与常规定义可能有所不同。** 给定长度为 $n$ 的序列 $[a_0,a_1,\ldots,a_{n-1}]$，以及一个正整数 $k$（$k\le n$）。定义一个 **划分** 如下：选择一个长度为 $k-1$ 的递增下标序列 $0

### 【测试程序方式】 选手可以在本题目录下使用如下命令编译得到可执行文件： ```bash g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static ``` 对于编译得到的可执行文件 `median`： - 可执行文件将从标准输入读入以下格式的数据： - 第一行包含两个非负整数 $c,t$。 - 接下来依次为每组测试数据。对于每组测试数据： - 第一行包含两个正整数 $n,k$。 - 第二行包含 $n$ 个正整数 $a_0,a_1,\ldots,a_{n-1}$。 - 可执行文件将输出以下格式的数据至标准输出： - 对于每组测试数据，输出一行一个正整数，表示平衡度的最大值。

无

### 【样例 $1$ 解释】 对于第一组测试数据，一种平衡度最大的划分为 $b_1=3$，$b_2=5$，$b_3=7$，其将原序列划分为 $4$ 个段 $[6,5,1]$、$[9,2]$、$[3,10]$、$[7,4,8]$，段中所有元素的中位数分别为 $5,9,10,7$，因此该划分的平衡度为 $\operatorname{Median}(\{5,9,10,7\})=9$。 对于第二组测试数据，一种平衡度最大的划分为 $b_1=2$，$b_2=4$，$b_3=6$，$b_4=8$，其将原序列划分为 $5$ 个段 $[5,7]$、$[3,10]$、$[8,2]$、$[9,1]$、$[6,4]$，段中所有元素的中位数分别为 $7,10,8,9,6$，因此该划分的平衡度为 $\operatorname{Median}(\{7,10,8,9,6\})=8$。 ### 【样例 $2$】 见选手目录下的 `median/median2.in` 与 `median/median2.ans`。 该样例满足测试点 $6$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `median/median3.in` 与 `median/median3.ans`。 该样例满足测试点 $9$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `median/median4.in` 与 `median/median4.ans`。 该样例满足测试点 $14$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `median/median5.in` 与 `median/median5.ans`。 该样例满足测试点 $18\sim20$ 的约束条件。 ### 【数据范围】 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： - $1\le t\le20$； - $5\le n\le10^6$，$2\le k\le n$，$N\le10^6$； - 对于所有 $0\le i5$ | ^ | | $18\sim20$ | ^ | ^ | $\le n$ | ^ | 特殊性质 $A$：对于所有 $0\le i