题解 暴风雪

· · 题解

小清新数据结构题。

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

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

先考虑求出这些分段。

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

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

直接对重链维护线段树，对于每个分段直接在线段树上操作，注意到重链权值单增，取 $\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，不确定大力卡常的高复杂度做法能否通过。