详细揭秘如何 d2t1 做两个小时。

Lehe · 2026-07-25 08:48:20 · 题解

声明：这是个完全做复杂了的搞笑做法，仅供娱乐。

upd：好像其实跟好几个题解做法等价。但是我觉得我多绕了一个前缀和考虑很搞笑啊，所以还是写上来了。

中位数的刻画很难不考虑直接二分，将 \ge \text{mid} 的记作 1，\lt \text{mid} 的记作 -1，则一个区间中位数 \ge \text{mid} 当且仅当区间内所有数的和 \ge 0。我们只要让这样的区间数 \ge 不满足的区间数即可。

考虑对这个序列做前缀和。于是一个区间产生贡献当且仅当 s_r \ge s_{l-1}。所以现在原问题变成了我们要选择 k+1 个位置 b_0 到 b_k，其中要求 b_0=0，b_k=n，然后问能否使得 s_{b_i} \le s_{b_{i+1}}（以下叫做上升对）的对数至少是 \lceil \frac{k}2 \rceil。

直觉上我们可能考虑去求最大的上升对个数，但是发现 k 的限制有点难处理。发现我们需要找出的位置大致只是 \frac k 2 量级的，而假设我们先不管最多 k+1 个点的要求，先随便选出 \lceil \frac{k}2 \rceil 个上升对并钦定它们无交，已经离限制非常接近了，因此我们可以猜测只需要在此基础上重复利用一些端点，将选出来的端点个数控制到 k+1 以内即可。同时需要注意到 s_i 和 s_{i+1} 的差绝对值恰好是 1，也就是形如一段折线，因此能额外有许多更好的性质。

首先判掉最简单的情况，即哪怕没有选 k 段的约束也无法达成。一个显然的性质是，一个序列的子序列的上升对数一定不超过它本身，因为考虑每次往子序列里插入一个数，答案不会变小。所以直接求出原序列上升对数，判掉即可。（场后想到了一个本质相同但更直观的考虑方式：在我们一开始的 1/-1 序列上贪心地把每个 1 划为一段，如果仍然不符合则无论如何都不可能有解）

接下来我们默认不考虑端点个数限制的前提下可以选出 \lceil \frac{k}2 \rceil 个上升对。考虑到 k 是偶数天然比奇数限制松，因此先考虑偶数情况。此时随便选出 \frac k 2 个上升对，看起来恰好是够的，甚至还多出来了一个端点。但是我们还限制了 b_0 和 b_k，因此我们必须把 b_0 和 b_k 选上，此时有 k+2 个端点，所以要想办法找到一种比较好的选点方法，合并掉一个重复使用的端点。

首先是一些比较平凡的情况：如果出现连续三个数形成上升段的情况一定可以缩掉中间那个被计算了两次的点。

排除掉这种情况以后一定大致形如每次连续下降一段长度然后上升一步，此时我们继续刻画，如果存在 N 字形，我们发现由于这四个点都被选了所以可以直接删掉中间山谷中的点，此时两个山峰相等所以不影响答案。

然后还有比较容易漏掉的一种：对于一个波形，直接贪心选会选上 1245，但是我们选择 135 三个点也可以含有两个上升对，也节省了一个端点。

最后还要注意端点一开始我们默认是孤立的，但是实际上如果端点也在上升对中也可以减少选的点数，所以也要判断。以及还有一个 corner：如果最后出现了一个 ^，那么三个点我们原来都选上了，但中间山峰处的点是不必要的，故可以删去。

可以说明以上几类考虑到了所有情况。特判 k=2 可以通过偶数的情况。

对于 k 是奇数，我们发现我们需要减少掉两个端点。基本上与偶数是类似的，只需判断能否存在两个上述情况即可。但是要注意一下连续两个波形的情况不可行，因为此时前后要求选上的点出现了矛盾。

其他的情况都是类似的。实现时由于边界有点烦可以偷懒写个 dp。

以下是一张图：

最后，在 k 很小的时候，由于我们前面的做法默认了 k 很大，但实际上 k 很小时可能出现我们判断的情形无法被全部选上的情况（例如波形要求 k \ge 4）。对于 k 很小跑暴力即可。我写了 k \le 10 为分界点，可以通过本题。