题解：P17143 [NOI 2026] 中位数（暂无数据）

· · 题解

首先显然二分答案，设二分的答案为 m，令 b_i=[a_i\ge m]，令 s_i 为 b 的前缀和数组。

只需要判断能否把原区间划分为 k 个区间，其中至少有 \left\lceil \dfrac{k}{2}\right\rceil 个区间的中位数为 1 即可。你可能会觉得，那不是只需要在这个序列中选取 \left\lceil \dfrac{k}{2}\right\rceil 个不重叠的、中位数为 1 的区间就行吗。但是很可惜，这是错的。比如 k=4，我选择了这样两个区间：..[..]..[..]..，这就把整个序列划分成了 5 个段，就错了，因为 t 个区间最多把序列划分成 2t+1 个段。但是如果相邻两个区间接壤，比如：..[..][..]..，就满足要求了。

计算一下，容易得到：对于 k 为奇数，至少有两对相接壤的区间；对于 k 为偶数，至少有一对相接壤的区间。

到这里就可以 dp 了，设 f_{i,j} 和 g_{i,j} 分别表示前 i 个位置，有 j 对相接壤的区间，且 i 是/不是一个选择的区间的结尾，最多能选出多少个中位数为 1 的区间。这里 j 只需要开到 2，把所有 >2 对相接壤的区间全部算成 2 个即可。转移有：

f_{i,j}=\max \begin{cases} \max\limits_{2(s_i-s_t)\ge i-t} g_{t,p}+1\ (p+1\ge j)\\ \max\limits_{2(s_i-s_t)\ge i-t} f_{t,j}+1\end{cases}\\ g_{i,j}=\max\{g_{i-1,j},f_{i-1,j}\}

把 2(s_i-s_t)\ge i-t 拆成 2s_i-i\ge 2s_t-t 即可用树状数组做到 \mathcal O(n\log^2 n)，但是这还不够。

注意到当 i\to i+1 时，2s_i-i 要么增加 1，要么减少 1。如果增加 1，就可以直接用查询 i 的答案和值为 2s_{i+1}-(i+1) 的 dp 值的最大值来作为这次查询的答案；如果减少 1，就可以用上一次查询 2s_i-i 这个值时得到的答案来作为这一次的答案，这样复杂度就是 \mathcal O(n\log n) 的了。

然后你写了，发现只能过 k>5 的部分。观察有一个样例形如 k=2，序列长成 00011000，你的程序为了满足有一对接壤的区间，选择了 000[1][1]000，这导致区间选多了。仔细思考一下，当 k>5 时，所有为了满足区间接壤数量的区间都可以被选择，所以能够通过。因此对于 k\le 5 的部分只要拼上一个 \mathcal O(nk\log n) 的暴力就可以了。状态就是把第二维的接壤数改成选择区间数，优化方法类似。

综上，当 k\le 5 时复杂度为 \mathcal O(nk\log n)；当 k>5 时复杂度为 \mathcal O(n\log n)。