hdu多校联训19.8.14

cjy2003 · 2019-08-15 21:09:20 · 个人记录

题意：

给一个 n 个点的树，初始时所有点的权值为 0，支持 m 次下列两种操作

1. 给 a 的子树内部到 a 距离 \bmod x=y 的点权值增加 w
2. 查询 a 的权值

题解：

考虑将 1 操作的 x 分成两部分

对于 x>S

我们可以处理出树的 bfs 序，于是只需要 O(\frac n S) 找出所有的段，要求支持区间 O(1) 加，单点 O(\sqrt n) 查询

我们再构造两个森林

对于第一个，点 x 的父亲满足下列条件的 dfs 序最小的点 y

1. dep_y=dep_x+1
2. dfn_y\ge dfn_x

对于第二个，点 x 的父亲满足下列条件的 dfs 序最大的点 y

1. dep_y=dep_x+1
2. dfn_y\le dfn_x+siz_x

对这两个森林进行重链剖分

则如果 x 的子树中存在距离为 d 的点，那 x 子树里所有的距离 x 为 d 的点里，bfs 序最小和最大的分别是第一个森林和第二个森林里 x 的第 d 个祖先

如果不存在，则要么 x 在某个森林里不存在第 d 个祖先，要么找到的这两个点不满足 第一个森林里的祖先的 bfs 序小于等于第二个森林里的祖先的 bfs 序

于是我们沿着重链向上跳，找到这些段的复杂度是 O(\frac n S +log (n))

对于 x\le S

我们将第一个操作的条件变为：对于 dfs 序 \ge dfn[a] 且 <dfn[a]+siz[a] ，深度 \bmod x=y 的点，权值加 w

这里要求区间加 O(\sqrt n)，查询 O(1)

可以对 dfs 序分块，维护一个三维数组 b，b[i][j][k] 表示对于第 k 块，深度模 i 余 j 的点一共增加了多少权值

于是总复杂度 O(n\sqrt n)

实际上，三维数组 b 占用空间非常大，而且访址速度非常慢，于是可以通过调整 S 来卡常数，实测 S 取 70 较优