题解 P7122 【Chino 与线段树】
Daniel13265
·
·
题解
设 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。