CF757G

· · 题解

大家好，我是 lxl 的粉丝，所以我用分块通过了这道题。

首先，因为 dis(i,j)=deep_i+deep_j-2\times deep_{lca(i,j)}，所以这个询问如当是求 \sum_{i=l}^rdeep_{lca(p_i,x)}。

如果没有修改并且不强制在线就是这道题。那我们就依次来解决强制在线和带修这两个问题。

对于强制在线，我们自然想到分块。

对于每个块，预处理整块到某个点的 LCA 的 deep 之和，空间 O(n\sqrt n)，但是时间 O(n^2)。

怎么优化呢？

注意到我们在求每一个块到另外的某一个点的答案的时候是可以以一种类似换根的方法来 O(1) 求的。

具体而言，我们先将块内的点在树上做好标记作为关键点。初始的时候答案自然为 0，之后考虑答案从 u 到 v 的转移。对于在 v 子树外的关键点，其和 v 的 LCA 相对于和 u 的 LCA 不会变化，对于 v 子树内的关键点，其 LCA 从 u 转移到 v。这样答案的增量自然就是 v 子树内的关键点数量乘上边权了。

然后散块的处理就非常朴素了，直接用欧拉序 O(1) 求 LCA。

然后考虑修改。注意到这个修改交换前后位置对整块的影响是非常小的。只有当一个点越过块的边界时才会影响预处理的答案。所以修改的时候不妨暴力维护每个块相对于最开始的状态移除了哪些点和加入了哪些点，然而实际上这些修改的内容的总量是远远达不到 O(n) 的。(如果我们要让所有点都不在原先的块内，即所有点都要越过边界的总的操作次数是 O(n\sqrt n) 次的。)

那么整块修改的点具体上限是多少呢？我们交换相邻两个块之间的一段显然是最优的（离得越远交换的代价越大）。那么不妨设每一个块左右两边都有这样长度为 k 段是要和相邻部分交换的。那么交换操作的总代价为 \sqrt nk^2（这里默认块长为 \sqrt n）,对一次询问的影响是 O(\sqrt nk) 的，当 k 取 n^{\frac14} 时卡满。（而实际上由于 k 这个时候只有十几，调一下块长就可以规避这些修改的影响。并且应该是没人想到卡分块所以实测 CF 上有影响的点总共只有 \sqrt n 级别。笔者也就是用这种写法过的。）

或者换一个维护的思路，我们维护对于每个边界有哪些点相对于最初状态越过了这个边界。那么对于整块的询问就是将序列划分成了三段，考虑在这三段之间的移动了的点（我们不关心在询问的整块之间移动的点）。这样越过边界的点就是严格 O(\sqrt n) 的了。询问也就是严格的 O(\sqrt n) 的了。

还没完！

由于这道题的正解是放给 n\log n 的，我们必须要进行一些卡常：

  1. 预处理时对树做 \sqrt n 次递归自然是不优秀的，不妨记录下来内向树和外向树的拓扑序把答案的更新放到序列上。

  2. 散块处理的时候如果长度大于 \frac{\sqrt n}2 考虑用整块答案减去小的那一部分。

  3. 大数组的查询常数是非常大的，所以对预处理的答案做前缀和然后询问的时候只查询一次。

  4. 尽量调小块长，要把空间卡满！

于是时间空间复杂度都是 O(n\sqrt n)。

代码写得太史山了，就不放了在这里了。

code