NOI D2T1

Register_int · 2026-07-22 14:32:02 · 题解

算是爆标吧，但是这个爆的应该全世界都会。

中位数问题可以考虑二分答案 x。将 \ge x 的数设为 1，<x 的数设为 -1，那一个区间的中位数 \ge x 当且仅当 \sum \ge 0。那么我们的目标就是判定：能否将序列划分为 k 段，使得有至少 m=\lceil k/2\rceil 段 \ge 0。

其实可以发现，我们直接选前 m 大独立成段就快赢了，因为这个时候最多只有 m+1 段 <0。而且最终方案的段不会太长，因为如果段内有 \ge 3 个 1，一定可以划分成两个段得到更优解。不妨假设序列的第 -1 个与第 n+2 的数都是 1，分讨：

• 对于 k 为偶数的情况，只要爆掉一个段。判断是否有两个 1 距离 \le 3 即可。
• 对于 k 为奇数的情况，要爆掉两个段。只有以下几种情况：
  • 两对距离 \le 3 的 1。
  • 三个 1，满足：相邻距离 \le 3，头尾距离 \le 5。
  • 四个 1，满足形如 1,1,-1,-1,-1,1,1 或 1,1,-1,-1,-1,1,-1,1（均可翻转）。注意此时段数要减一。

我们几乎解决了所有情况。可以发现对于小的 k，这个构造不一定对。所以单独解决：

至此本题解决，时间复杂度 \mathcal{O}(n\log n)。换成扫描线，每次加入一个 1 只需要检查前后 3 个 1。查询前驱后继用压位并查集做，即可做到 \mathcal{O}(n)。