2023-08-05 模拟赛

有点超出我的预设。

T1

source: ABC267F

签到题，直径性质，实现得好的可以利用 dfn 序的性质 $\Theta(n)$，我赛时写的 $\Theta(n \log n)$。

code

T3

source: CF1651F

第一眼看上去是对塔分块，有一个比较暴力的 $\Theta(n \sqrt{n})$ 的做法能冲过去。本来准备卡的，结果发现不是很能卡住，所以就分了 $3$ 档，写分块的至少 $60pts$，写的好的能直接冲过去。

正解，首先需要观察，一个怪兽能造成的贡献可以拆分成两种方式，第一种是一段区间直接推平，第二种是对于某一个塔削弱血量。考虑颜色段均摊，维护场上的若干个连续段 $[l, r]$。

如果遇到 $l=r$，直接暴力算。
遇到 $l \lt r$，这代表被以前的询问推平的一段区间，问题成了给定初始生命 $hp$，时间差 $T$，左右端点 $[l,r]$ ，问是否能再次推平这个区间，或者是在这个区间停下。

比较关键的步骤是将塔的回血操作看成分段的一次函数，具体是

$$ \begin{cases} r_i t, & t \le \lceil \frac{c_i}{r_i} \rceil \\ c_i, & t > \lceil \frac{c_i}{r_i} \rceil \end{cases} $$

以位置为下标，可以上可持久化线段树，合并一次函数就行了。于是得到了一个主席树上二分的单 $log$ 做法。

code nlog
code nsqrt