P5979 题解

· · 题解

首先，容易得到一个朴素 dp：设 f_i 为前 i 个人划分的最大组，枚举最后一次划分点，有

f_i=\max(f_j+1)(\max(c_{j+1},c_{j+2}...c_i)\le i-j\le \min(d_{j+1},d_{j+2}...d_i))

对于计数，设 g_i 为 f_i 取最大值的方案数，把所有能让 f 取最大值的转移的 g 加起来即可。

考虑分治优化。

记当前区间为 [l,r]。

首先找到 [l+1,r] 中 c_k 最大的 k，先递归处理 [l,k-1]，然后考虑 [l,k-1] 对 [k,r] 的贡献，最后递归处理 [k,r]。

这样处理有一个性质：[l,k-1] 对 [k,r] 更新时，c 最大的值永远是 c_k，这样就压了一个限制。

对于左区间长度更长的情况，枚举右区间的每个点 i，则左区间内能更新这个点 j 的最小值是 \min(k-1,i-c_k)，最大值是 \max(l,lim_i)。其中 lim_i 为最大的满足 d 限制的 j。

对于右区间长度更长的情况，枚举左区间的每个点 j，则右区间内能被这个点更新的 i 的最小值是 \max(k,j+c_k)，最大值是 \min(r,lim2_j)。其中 lim2_j 为最大的满足 d 限制的 i。

对于 lim,lim2 的处理，可以推出来有单调性，双指针 +multiset 可以在 O(nlogn) 的复杂度预处理。

用线段树维护 f 和 g，我们需要支持以下操作：

  1. 查询区间 c 最大值和位置。
  2. 查询区间 f 最大值。
  3. 区间 f 与一个数取 \max 并维护 g。

复杂度证明类似启发式分裂，每层用较小区间的复杂度处理。

然后如果你和我一样大常数，可能需要一个剪枝：枚举右区间 lim_i\ge k 时，或者枚举左区间 i+c_k\ge r 时，之后也不会有合法的区间，直接 break。

代码比较丑，就不放了。