自动搬运

查看原文

来自洛谷，原作者为

	Kenma 入得此门不回首，无需宣之于口

搬运于2025-08-24 23:16:17，当前版本为作者最后更新于2025-05-20 15:58:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

提供一种比官解劣的做法。

用一节 whk 自习口胡出来的。

思路分析

首先换根是假的，我们依然维护以 $1$ 为根的子树和即可。

考虑根号相关数据结构。

把 $A$ 分块，块长为 $B$，那么我们分散块和整块考虑。

对于散块，散块的总块长之和为 $O(nB)$，这一部分直接维护链加子树和，使用树上差分相关套路做到 $O(nB\log n)$。

对于整块，我们预处理系数 $b_{i,j}$ 表示进行第 $i$ 块内加 $1$，第 $j$ 个点的子树会加 $b_{i,j}$。$b$ 的处理可以树上差分求两次子树和做到 $O(\frac{n^2}{B})$。

因为要求空间线性，所以我们需要逐块处理。

总体复杂度为 $O(nB\log n+\frac{n^2}{B})$，平衡复杂度后为 $O(n \sqrt{n \log n})$。

关于链加子树和的维护，也可以使用更简单的树剖 + BIT，总体复杂度为 $O(nB\log^2 n+\frac{n^2}{B})$，平衡复杂度后为 $O(n \sqrt{n} \log n)$，常数很小。