笛卡尔树和其 RMQ
__ryp__
·
·
个人记录
有一个东西：
\begin{aligned}
E(x) &= \sum\limits_{i=1}^V\sum\limits_{j=1}^V \dfrac {\lvert j - i + 1\rvert} {V^2}\\
&= \sum\limits_{i=1}^V\bigg(\sum\limits_{j=i}^V \dfrac{j - i + 1}{V^2} + \sum\limits_{j=1}^{i-1}\dfrac{i-j+1}{V^2}\bigg)\\
&=\sum\limits_{i=1}^V \dfrac 1{V^2}\bigg(\sum\limits_{j=1}^{V - i + 1} 1 + \sum\limits_{j=2}^i 1\bigg) \\
&=\dfrac{1}{V^2} \sum\limits_{i=1}^V\bigg(\dfrac 1 2 (V-i+2)(V-i+1) + \dfrac{1}{2} (i+2)(i - 1)\bigg)\\
\end{aligned}