2024/03/23(#24)：向命运拒绝在黑暗中湮灭

再来一次吧！

[CF1707E] Replace

Portal.

首先答案上界是 $2n$，大概是先转一圈然后再依次扩展。

我们可以维护一个 $f^{2^k}(l,r)$ 来用于在询问的时候快速回答，但是 $(l,r)$ 的数量是爆炸的 $O(n^2)$。现在的问题是如何减少 $f(l,r)$ 需要的数量。

所以要找性质。我们有在 $[l_1,r_1]$ 和 $[l_2,r_2]$ 有交时，令 $[l,r] = [l_1,r_1]\cup [l_2,r_2]$，那么 $f^k ([l,r])=f^k ([l_1,r_1]) \cup f^k ([l_2,r_2])$。

因为它们的值域相交，所以 $f (l_1,r_1) \cap f (l_2,r_2)\ne \varnothing$，而在它们有交集的前提下，有 $f (l_1,r_1) \cup f (l_2,r_2)=f(\min\{l_1,l_2\},\max\{r_1,r_2\})$，对这个东西进行数学归纳，所以上面的那个是对的。

也就是说我们使用 ST 表维护每个 $f^{2^k}$ 的值即可，内部的数量级从 $O(n^2)$ 降低到了 $O(n\log n)$，总时间复杂度 $O((n+q)\log ^2 n)$。代码。

[CF1844G] Tree Weights

Portal.

考虑依次对方程在模 $2^k$ 意义下进行求解，然后递推即可。代码。

[CF1918F] Caterpillar on a Tree

Portal.

直接贪心就行了。代码。