题解：P9755 [CSP-S 2023] 种树

二分答案 $m$。

我们需要判断是否存在一个序列 $\{d_n\}$ 表示对于每个 $i$，第 $i$ 棵树如果在第 $d_i$ 天种下，都要达到 $a_i$ 的高度。

显然一棵树种的越早越好。我们可以求解一个 $f(i)$ 表示第 $i$ 棵树最晚在第几天种可以满足要求。

假设我们已经求好了。不难发现一个必要条件是：

> 对于所有 $1 \le i \le n$，满足 $f(u) \le i$ 的数量必须 $\le i$。

但不充分。

显然对于一条树边 $(fa_u, u)$ 而言，有 $d_{fa_u} \le d_u - 1$。这是因为你从 $1$ 扩展到 $u$ 必须经过 $fa_u$。那么我们可以 $\operatorname{chkmin}(f_{fa_u}, f_u-1)$，以得到实际的 $f$。

此时上面的条件充分。

> 简洁证明：
> 
> 首先这样做完后 $f$ 一定是一个小根堆的形态。即祖宗的权值一定 $\le$ 儿子的权值。
>
> 那么所有满足 $f(u) \le i$ 的 $u$ 在树上**一定是一个包含根的连通块**。令这样的 $u$ 的数量为 $c$。显然我们可以用 $c$ 天时间将这些点上种上树。因为 $c \le i$ 所以这些点都可以满足要求。
>
> 对于所有的 $i$，上面的分析均成立。所以这样做是正确的。

---

考虑求解更新前的 $f(i)$，即第 $i$ 棵树最晚在第几天种可以满足要求。

令 $s(i, l, r)$ 表示第 $i$ 棵树在第 $l \sim r$ 天内增长的高度。那么原问题等价于是否对于所有 $i$ 都满足：

$$
s(i, d_i, m) \ge a_i
$$

显然可以差分。令 $g(i, j) = s(i, 1, j)$，则 $s(i, l, r) = g(i, r) - g(i, l - 1)$。即：

$$
g(i, m) - g(i, d_i) \ge a_i
$$

注意到 $d_i$ 越小越好。所以我们二分 $d_i$。所以现在的任务是求解 $g(i, m)$。由定义知：

$$
g(i, m) = \sum_{j=1}^m \max(b_i + j \times c_i, 1)
$$

分类讨论：

- $c_i = 0$：题目保证 $b_i \ge 1$，所以 $\max(b_i,1) = b_i$。所以 $g(i, m) = \sum_{j=1}^m b_i = m\times b_i$。
- $c_i > 0$：显然 $i$ 越大 $b_i + j \times c_i$ 大。注意到当 $j < \lceil \frac{1-b_i}{c_i} \rceil$ 时 $b_i + j \times c_i < 1$。所以前面是很多 $1$，后面是一个等差数列求和。
- $c_i < 0$。同理。显然 $i$ 越大 $b_i + j \times c_i$ 小。注意到当 $j > \lfloor \frac{1-b_i}{c_i} \rfloor$ 时 $b_i + j \times c_i < 1$。所以前面是一个等差数列求和，后面是很多 $1$。

正在渲染内容...