自动搬运

查看原文

来自洛谷，原作者为

	Zzzcr **

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

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

以下是正文

当 $n=2^k$ 时，考虑树形 dp，需要合并左子树和右子树的答案，可以将左子树右链和右子树左链上的点错位相配对，配对的结点都可以用同一个集合覆盖。有 $f(2^k)=2f(2^{k-1})-k+1$ 。在两侧待合并链的长度不同时，可以合并的点数即两侧点数较小值，所以 $f(n)=f(\left \lfloor \frac{n}{2} \right \rfloor)+f(\left \lceil \frac{n}{2} \right \rceil)-\left \lfloor \log_{2}{\left \lceil \frac{n}{2} \right \rceil } \right \rfloor (n\ge4)$，记忆化搜索即可解决单点问题。

结论：$f_{1...n}$ 可以被划分为 $\mathcal{O}(\log n)$ 段 $d=1$ 的等差数列和 $\mathcal{O}(\log n)$ 个值相同的连续段。

考虑在一棵满二叉树上按照顺序依次向下挂一对儿子，根据之前的分析，容易得出在这个过程的前半，答案每次加一，后半答案保持不变，而满二叉树的深度是 $\mathcal{O}(\log n)$ 级别的，所以结论是正确的。

预处理出每段和，段间前缀和，可以 $\mathcal{O}(1)$ 找到一个值所属的段，总复杂度 $\mathcal{O}(q+\log n)$。