NOI2026 线段 + 中位数

赛时思路。

线段

首先看到题目，感觉这个东西直接建图很没有前途，于是我们考虑刻画一下这个可能的答案的形态，于是发现一个性质就是如果没个位置被覆盖了大于等于 \(3\) 次就直接死了，然后我们发现这个条件只要判掉不联通的情况就是充要的。

有了这个东西之后就感觉状态比较自然了：设 \(dp_{i,j,k}\) 表示前 \(i\) 个位置，然后目前最远被覆盖到了 \(j\)，用了 \(k\) 条线段的答案。

这个转移就是枚举一条从 \(i\) 开始的线段 \(i, r\)，有转移：

\[dp_{i,j, k} \to dp_{{min(j, r) + 1}, {max(j, r)}, {k + 1}} \]

记得特判掉 \(j = r\) 的情况，这个直接转移到答案。

然后就是不选：

\[dp_{i, j, k} \to dp_{i + 1, j, k} \]

还得特判 \(i = j\) 的情况，同上。

接下来就是初值的问题，我们先判掉选两条相同线段的情况，然后我们就考虑对于 \(k = 1\) 的初值就是直接选一条线段（这个赋初值的位置要在选线段的转移之后），然后对于 \(k = 2\) 的初值就是枚举选哪两条就可以了。

分析一下复杂度就是时间上是 \(O(nmk + n^2)\)，但是空间开不下，于是我们发现 \(k\) 是固定转移到 \(k + 1\) 的，于是把 \(k\) 作为阶段来做滚动数组就行了。

空间复杂度是 \(O(m^2k)\) 的，在 noi 的机子上跑了 \(1.4s\)。

中位数

看到题就直接二分中位数，接下来问题就转化成了划分成 \(t\) 段，使得至少有 \(\lfloor{\frac{t + 1}{2}}\rfloor\) 端和大于等于零。

那么我们可以分类讨论：

对于 \(t\) 为偶数。

我们发现这样的东西形状上一定符合要么靠着左右端点有一段可以的，要么中间有一段相邻两个都可以的，只要有一个这样的形状然后在这样的形状外面有剩下段数个 \(1\) 就行了，对于靠着左右端点的，维护出来最短的可行段，然后剩下的直接用前后缀和求出来有多少个 \(1\) 就行了，对于有两个相邻的，可以维护出来每个点向左向右最短的合法端，然后拼一下就可以了。

对于 \(t\) 为奇数。

情况比较多，但是大致还是上面几种组合一下，然后有一些情况，还是类似的去维护一下，这边讲一下比较难的两种：

对于有两段相邻的我们发现我们可以把这个占用的 \(1\) 的个数挂到右端点和左端点上，然后分别取一下前后缀最小值然后对应位置加起来就可以了。

对于连续三个相邻的，我们可以使用树状数组做到一个 \(\log\)，但是我们思考一下就可以发现中间那段最优秀的和肯定为 \(0\)，于是就只需要单点查询，就可以做到线性。

赛时写的复杂度为 \(O(n \log^2 n)\) 极限通过，另外一个 \(\log\) 就是上面维护的 \(\log\)，noi 机子上跑了 \(0.85s\)，但是优化到单 \(\log\) 不困难。