[JZOJ1026模拟] 苹果

考虑每个节点对区间的贡献

考虑要是一个节点的左儿子产生贡献,那么贡献区间的 L 是这个左儿子的左端点,假如我们设这个区间长度是 2^w ,贡献区间所有可能的右端点是 [L+2^w-1,L+2^{w+1}-1)

那么一层来看的话,所有的右端点总长是 2^{n-1} 的。

那么这块的总贡献是

\sum_{i=1}^{n-1} { i \cdot 2^{n-1} } = 2^{n-2} \cdot (n+1) \cdot n

现在考虑右儿子,类似地,我们单点可用的区间右端点是:

2^n - (L+2^w) +1

那么一层的话就是 2^{n+i-2} - 2^{n-1} + 2^{i-1}

那么这块的总贡献是

\sum_{i=1}^{n} { i \cdot ( 2^{n+i-2} - 2^{n-1} + 2^{i-1} ) }

那么把这个式子改写一下 ( 设 \lambda = 2^0+2^{n-1}

\sum_{i=1}^n { i \cdot \lambda \cdot 2^{i-1} } - \sum_{i=1}^n { i \cdot 2^{n-1} }

化简,求总答案:

A=2^{n-2}\cdot \left( n+1 \right) \cdot n

B=\lambda \cdot \left( n\cdot 2^n-2^n \right) +1-2^{n-2}\cdot \left( n+1 \right) \cdot n

\text{ans}=2\cdot \left( A+B \right)

=\left[ \left( n-1 \right) \cdot 2^{n+1}+2 \right] \cdot \lambda \cdot \ \left( \frac{\left( 2^n+1 \right) \cdot 2^n}{2} \right) ^{-1}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据