自动搬运

查看原文

来自洛谷，原作者为

	Daniel13265 **

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

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

以下是正文

---

设 $d\left(n\right)$ 表示一棵 $n$ 个叶子结点的线段树的深度，那么有 $d\left(1\right)=1$ 与

$$\begin{aligned} d\left(2n\right)&=d\left(n\right)+1,\\ d\left(2n+1\right)&=\max\left\{d\left(n+1\right),d\left(n\right)\right\}+1. \end{aligned} $$

所以

$$d\left(n\right)=\left\lceil\log n\right\rceil+1.$$

我们又有

$$\begin{aligned} f\left(2n\right)&=2^{d\left(n\right)+1}+f\left(n\right),\\ f\left(2n+1\right)&=\begin{cases} 2^{d\left(n\right)}+f\left(n+1\right), &d\left(n+1\right)>d\left(n\right),\\ 2^{d\left(n\right)+1}+f\left(n\right), &d\left(n+1\right)\le d\left(n\right). \end{cases} \end{aligned} $$

按 $n$ 的二进制位从高位向低位递推。发现 $d\left(n+1\right)>d\left(n\right)$ 当且仅当 $n=2^k\left(k\in\N\right)$，因此 $n$ 最高 $\texttt1$ 位后的全 $\texttt0$ 段这一部分的答案可以直接计算，之后的 $\texttt1$ 位就一定是第二种情况，于是第一段全 $\texttt0$ 位后的 $\texttt0$ 位就与 $\texttt1$ 位一样了。

有了这点，我们就容易发现

$$f\left(n\right)=\begin{cases} 2^{x+1}-1, &n=2^x\left(x\in\N\right),\\ 2^{x+2}-2^{x-y+1}+1, &n=2^x+2^y+t\left(x,y\in\N,0\le t<2^y<2^x\right). \end{cases} $$

现在我们要对 $f$ 求和。我们可以分别求出 $n=1,2,3,\dots,b$ 时的和与 $n=1,2,3,\dots,a-1$ 时的和，然后作差得出答案，所以我们现在要对于 $N=a-1$ 和 $N=b$ 求

$$\sum_{n=1}^Nf\left(n\right).$$

若 $N=2^X\left(X\in\N\right)$，那么我们单独计算 $f\left(N\right)$ 然后并计算 $N$ 减去一后的答案，求和就可以得到答案。所以我们假设 $N=2^X+2^Y+T\left(X,Y\in\N,0\le T<2^Y<2^X\right)$，那么

$$\begin{aligned} \sum_{n=1}^Nf\left(n\right)=&\sum_{x=0}^{X-1}\left(2^{x+1}-1+\sum_{y=0}^{x-1}2^y\left(2^{x+2}-2^{x-y+1}+1\right)\right)+2^{X+1}-1\\ &\qquad+\sum_{y=0}^{Y-1}2^y\left(2^{X+2}-2^{X-y+1}+1\right)+\left(T+1\right)\left(2^{X+2}-2^{X-Y+1}+1\right)\\ =&3\times2^X-2^{X+1}X-2X+\frac{2^{2X+2}-13}3+2^{X+1}-1\\ &\qquad+\left(2^{X+2}+1\right)\left(2^Y-1\right)-Y\times2^{X+1}+\left(T+1\right)\left(2^{X+2}-2^{X-Y+1}+1\right). \end{aligned} $$

于是就可以计算了。你可能需要一个高精度板子。时间复杂度 $\sout{O\left(\log b\log\log b\right)}$，空间复杂度 $\sout{O\left(\log b\right)}$。人生苦短，我用 Ruby。