CF342E 操作分块

xfrvq · 2022-08-20 22:04:44 · 题解

\tt Link，\tt^{\ast}2400。

明明是 \tt LCT 或点分树，我却只想操作分块。

我们把操作序列以 \sqrt m 为块长分块。

一个询问的答案是如下红点的贡献的 \min。

• 和询问同块的修改
• 在询问所在块之前的块的修改

第一类，我们枚举每个操作块，从前往后扫，询问直接用当前的红点的距离取 \min。

一个块的操作仅会带来根号个红点。如何快速算距离？考虑 O(n\log n)-O(1) 的 \tt LCA。

第二类，我们用一个 ans 数组记录下当上一个操作块刚刚结束时，每个点的答案。

这个可以在扫完这个块之后，在树上跑 \tt dfs，更新这根号个红点的新贡献。

准确来说是跑两遍 \tt dfs，第一遍用儿子更新父亲，第二遍用父亲更新儿子。

总复杂度 O(m\sqrt m)。