Luogu5528 [Ynoi2012] WC,THUWC,CTSC与APIO2017

发表于 更新于 分类于 ， ， 阅读次数：

题意：维护一颗有根树，点有点权，边权均为 ，支持下列操作 ：

  • 将 子树中与 距离模 为 的点权加上 。

  • 查询点 的权值。

，时限 。

和 Luogu5309 有点类似，但难度超出许多。

取阈值 。

对于每个 分别计算。

将点按照深度 的值分组，显然，一次修改只会涉及 组中的点。

对每个组按照 序排序，子树的约束相当于一个区间。

可以一开始就把点按照 序排序，然后使用桶分类，这样组中自然有序。

查找需要修改的区间时需要 std::lower_bound，可以进一步离线变为线性，不过由于这部分常数不算大，没必要。

注意到修改有 个，贡献到询问的次数共 ，使用 修改 查询的分块即可。

由于没有强制在线，对每个 逐次处理可以做到 空间。

一个点的所有 级后代在 序上排列为一个连续段。

可以将问题转化为 次区间加法，使用 修改 查询的分块即可。

问题在于如何找到修改的左右端点。

可以模仿前面的做法，在对应深度的一层二分，但是需要多个 。

定义一个点的 为：所有兄弟的 序最小的儿子。

这样，跳 次 后，若还在自己子树内，就能得到最左侧的点，右侧点类似。不难发现这就是 级祖先问题。

可以使用长链剖分做到 预处理， 询问。但这做法常数较大且实现略为繁琐。

然而，我们的查询是有性质的：查询一个点的 级祖先。

可以使用重链剖分，跳过的重链一共是 条的，由此导致的额外复杂度可不计。

综上，令 ，时间复杂度 ，空间复杂度 。