美食殿堂

所爱隔山海,山海亦须平

CF1425I Impressive Harvesting of The Orchard

暴力。暴力。暴力。

根号分治,生长时间大于 $B$ 的直接按 DFS 序分块,每次先把恰好当前时间长出的果子放回去,再枚举每一段暴力取出,挂到后面对应的时间下面。空间复杂度 $O(\frac{N^2}{B})$,时间复杂度 $O(Q\sqrt N+\frac{N^2}{B})$。

对于生长时间小于等于 $B$ 的,每种生长时间都开一棵线段树存储距离成熟还需多久。

查询时直接找到所有 $0$ 的连续段,然后覆盖成生长时间。修改则直接打标记。注意可以直接将原树当成一棵三叉线段树来搞。

社论也不知道在搞什么,大概就是上面这样,然而复杂度是错的,将底层结点分成两组随便卡卡就没了。

发现这个东西本质其实就是个假的 Beats,被取最值的数会被额外加上某个固定的数。