自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:59:18，当前版本为作者最后更新于2023-03-11 20:28:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

小清新数据结构题。

容易发现，单点加其实是把该点到根的路径上的 $f$ 值分段取 $\max$。

考虑其祖先 $x$，如果 $x$ 的位置进行了分段。那么 $x$ 具有另外一个深度不小于 $x$ 到叶子距离的子树，那么分的段数显然是根号的。

先考虑求出这些分段。

轻重剖。如果从轻边跳上来，直接对整棵树的每一层维护个 BIT，直接 $O(\log n)$ 求和重置答案。

对于从重边跳上来，维护某个点所有轻子树每一层的和，然后对 $x$ 的祖先距离进行根号分治。

$\le \sqrt n$ 的直接做，对于 $>\sqrt n$ 的，把存在一个轻子树深度不小于 $\sqrt n$ 的结点标记出来，只有这些结点可能新增分段。

直接对重链维护线段树，对于每个分段直接在线段树上操作，注意到重链权值单增，取 $\max$ 可以维护个区间最小最大值然后大力递归。

然后直接做是 $O(n\sqrt n\log n)$ 的，可以获得 50 分。

可以优化至 $n\sqrt{n\log n}$：把距离 $x$ 不超过 $\sqrt{n\log n}$ 的点暴力修改，剩余不超过 $\sqrt{n/\log n}$ 个线段树操作。

有若干优化到 $O(n\sqrt n)$ 的方法，这里介绍一个最优雅的 zky 的方法。

注意到所有区间的长度对数值之和为 $O(\sqrt n)$。就是 $\sum a_i \le n$，那么 $\sum \log(a_i-a_{i-1})=O(\sqrt n))$，这是个经典结论。

还是贺个证明，考虑 $a$ 的差分数组翻转后设为 $b$，那么就是 $\sum b_i \times i\le n$，$\sum \log(b_i)=O(\sqrt n)$。记 $|b|=m$，考虑均值不等式 $\prod (b_i\times i)^{1/m}\le (\sum b_i \times i)/m\le n/m$，也即 $\prod b_i\le (n/m)^m/m!$。两边取对数，把 $\log(m!)$ 近似为 $\log$ 的积分得到 $\sum \log(b_i)\le m(\log n-\log m)-(m\log m-m)=m(\log n-2\log m)+m$。导一下发现是 $\log n-2\log m-1$，所以 $m$ 大概就是 $\sqrt n$ 的时候最大（因为 $m\le \sqrt n$，常数项不影响），取到 $O(\sqrt n)$。

可以发现，修改涉及到的点数是 $O(\sqrt n)$。具体来说就是，一个区间在线段树上被拆成了 $O(\log(r-l+1))$ 个区间。然后考虑所有这 $O(\sqrt n)$ 个区间到根的并，可以发现，这里涉及到的结点就是 $O(\log^2 n)$ 个重链前缀拆出来的结点，和 $O(\sqrt n)$ 个左右子树都被涉及的结点。

那么做一些精细的实现即可做到 $O(n\sqrt n)$。

为了放过大常数的正解，将时间限制开到了 4.5s，不确定大力卡常的高复杂度做法能否通过。