题解

思路

从直接枚举窗口逐步优化到动态维护次序统计量；满分算法把“最大中位数”转化为关于候选值的单调判定，再使用二分答案。

子任务一：枚举并排序

枚举所有长度至少为 $k$ 的子数组，复制并排序，直接读取题目定义的位置。复杂度为 $O(n^3\log n)$，足以处理 $n\le40$。

子任务二：动态维护次序统计量

固定左端点并逐步扩展右端点。把当前子数组的元素加入值域树状数组；当长度至少为 $k$ 时，用树状数组二分第 $\lfloor(x+1)/2\rfloor$ 小的元素。复杂度为 $O(n^2\log n)$，适用于 $n\le2000$。

子任务三：二分答案

二分一个候选值 $x$。把每个 $a_i\ge x$ 记为 $+1$，其余记为 $-1$。一个子数组的中位数至少为 $x$，当且仅当它的变换后元素和严格大于零。

记前缀和为 $s_i$。扫描右端点 $i\ge k$，维护 $s_0,\ldots,s_{i-k}$ 的最小值；若 $s_i$ 大于这个最小值，就存在合法子数组。该判定为 $O(n)$，总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

注意严格大于零不可写成大于等于零；偶数长度时，这正好区分题目采用的较小中位数。

做法

二分 $x$，将 $a_i\ge x$ 映射为 $1$，其余映射为 $-1$。计算前缀和并扫描右端点；扫描到 $i$ 时先把 $s_{i-k}$ 纳入前缀最小值。若当前前缀和严格大于此前缀最小值，则接受 $x$。最终输出最大的可接受候选值。

复杂度

满分算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。