题解 【SR2.7-T5】【八云蓝自动机Ⅱ】

· · 题解

因为要求的是固定右端点为 p，左端点在 [l,r] 之间的所有答案之和，于是我们考虑扫描线，从 1 到 m 依次枚举右端点位置，动态维护所有左端点对应的答案

那么显然只有当前枚举到的位置是三操作时，才会对答案产生影响

不难求出 x 上一次被涉及到的操作是 j

  1. 如果 j 操作是操作一，那么对于 l \le j，答案增加了 k，对于 l > j，答案增加了 a_x

  2. 如果 j 操作是操作二，那么对于 l \le j，对答案的影响等价于在执行 j 操作前，进行 3 y 操作产生的影响，对于 l > j，答案增加了 a_x

显然 1 是容易处理的，而对于 2，我们将这个操作的影响转化为了一次区间加，和执行另一次操作的影响，依据这种分解关系，我们可以建立出一颗操作树，从儿子 u 向父亲 v 连边，表示执行 u 操作的影响，等价于执行 u 操作代表的一次区间加，加上执行 v 操作的影响

这样的一些操作原本是不存在的，但是我们只会在二操作前查询这次操作对应的 x,y，添加上这些操作后，操作树（其实是森林）至多有 2m 个节点

为了方便一点，我们可以在操作一执行后也建立一个节点，这样 1 情况也可以转化为 2 情况

现在的题意是这样的：给你一个操作森林，每个节点上写着一个区间 [l,r] 和 v，执行这个节点的操作代表给一个序列 [l,r] 区间加上 v

现在要支持执行一个点到根路径上所有点的操作（称为“修改”），以及查询这个序列的一个区间之和（称为“查询”）

乍一看这个东西完全不可做，但实际上这个森林具有性质：

  1. 每个点往根走，经过的 [l,r] 区间彼此不相交，且后经过的区间永远在先经过的左边

  2. 三操作建立出的节点没有孩子，二操作建立出的节点至多有一个二操作的孩子

性质一意味着，一次修改对一次查询的贡献，我们是可以快速计算的，首先 [l,r] 之和可以转化为 [1,r] - [1,l - 1]，也就是前缀查询

由于性质一，所有与 [1,x] 有关的节点一定是路径上的一段前缀，我们只需要找到 x 落在路径上哪个节点的区间 [l,r] 内，然后贡献就是 (x - l + 1) \times v + sum_{fa_x}，sum_u 表示的是从 u 所在子树根到 u 路径上所有 (r - l + 1) \times v 之和

而性质二意味着，我们对于这颗树进行重链剖分，从 u 往上跳只需跳 O(1) 条轻边即可到达根

设想一下，如果所有查询在所有修改后，该怎么做？dfs 这颗树，计算每个点被执行的次数，然后差分进行区间加，最后算一遍前缀和

这实际上意味着，我们可以在 O(n) 的时间内，执行操作森林任意点集的修改操作

而我们又可以快速计算一次修改对一次查询的贡献，于是做法已经呼之欲出了：定期重构，或者叫对时间轴分块

我们每 \sqrt m 次修改操作后重构一次，重构就是结算尚未进行的修改操作对于我们所维护的答案数组的贡献，而每遇到查询，先在答案数组里面求一下答案，然后再枚举没有进行的修改操作，与这个查询结算贡献

但计算一次修改对一次查询的贡献时，有一个问题是如何确定 x 在路径上哪个节点的区间内

一个 naive 的做法是倍增，最终复杂度大概是 n \sqrt {n \log n}，我也不知道你能不能过

比较正确的做法是，树剖，每条链上对于每个节点 u 的区间 [l,r]，直接给 [l,r] 标记上 u，然后用分块 O(n \sqrt n) 预处理，O(1) 查询之类的，但我觉得空间会很难做到 O(n)

考虑个简单的做法，直接对树进行 dfs，然后动态对每个节点，维护其到根路径上，每个位置所属的节点，类似 K 级祖先那个离线的 O(1) 查询做法，v 节点的信息可以直接由其父亲 u 的信息继承，再给自己的区间 [l,r] 覆盖上 v

但相信没有人愿意写可持久化分块，也相信开不下空间，于是我们二次离线，然后枚举修改给查询加贡献

综上，如果视 n,m,q 同阶，我们得到了一个时间复杂度为 O(n \sqrt n)，空间复杂度为 O(n) 的做法