题解：P11587 [KTSC 2022 R2] 编程测试

dyc2022 · 2026-09-14 16:56:47 · 题解

更好的阅读体验

凸凸的壳？！？！

首先答案是有单调性的。那么假设我现在想要二分答案，思考如何判断一个答案 ans 是否合法。

考虑把原问题转化为一个二分图匹配问题。左部点就是总共 (r - l + 1) \cdot ans 个我们希望凑出的问题，右部点就是我们可以拿出的问题。具体地，在位置 i，有 a_i 个问题可以贡献到难度为 i 的预期问题上；同时有 b_i 个问题可以分别贡献到难度为 i 和 i+1 的预期问题上。因此 a_i 个点每个点向总共 ans 个难度为 i 的预期问题连一条边，b_i 个点每个店向总共 2\cdot ans 个难度为 i, i+1 的预期问题连一条边。如图是一种连边方式的示例。

那么有解的条件就是对于左部点存在完美匹配。由 Hall 定理，有解的充要条件就是对于左部点的每个子集，其邻域大小都 \ge 这个子集的大小。进一步注意到，假设这个子集可以划分成若干个下标上的连续段，那么每个连续段的邻域是不交的。也就是说，我们只需要考虑这个子集表现为下标上连续的一段的情况。至此我们可以设计出一个多项式时间的判定算法。

假设现在询问的区间是 [L, R]。那么可以刻画出 ans 合法的条件，也就是对于 \forall [l, r] \subseteq [L, R]，有 \sum \limits_{i = l} ^ r a_i + \sum \limits_{i = l-1}^r b_i \ge (r-l+1) \cdot ans。记 a, b 的前缀和数组分别是 sa, sb，原式可以写成

考虑用 l 代替 l-1，则 l, r 的限制变为了 L-1 \le l < r \le R。则上式可以写成

这个很像斜率的形式！你发现其实现在已经不需要二分答案了；记 P_i(i, sa_i + sb_i), Q_i(i, sa_i + sb_{i - 1})，则答案就是取 L-1 \le i < j \le R，Q_i 和 P_j 连线斜率的最小值，再向下取整。

下文中所有 L 为原问题中的 L-1。则所求解的就是选取 L \le i < j \le R，Q_i 和 P_j 连线的最小斜率。

对于这个转化过后的问题，考虑进行猫树分治。现在假设分治区间为 [l, r]，区间中点为 mid。则有三种可能产生贡献的 i, j：i, j 都位于 mid 左侧，都位于 mid 右侧，或者 i \le mid < j。

先考虑 i, j 都位于 mid 左侧的情况。则我们可以预处理出一个数字 lans_k，表示 [k, mid] 区间内 P_i 和 Q_j 连线斜率的最小值。那么我们只需要对于每个 k，求出对于所有 j \isin (k, mid]，Q_k 和 P_j 的连线最小斜率。

那么显然这个 P_j 一定会在 j \isin (k, mid] 的点构成的下凸壳上，如图。从左往右维护这个下凸壳，每次加入一个 P_k，然后再凸壳上三分出过 Q_k 的切线即可。

对每个 Q_k 的结果取一个后缀 \min 就可以得到 lans 数组。