题意：

最低等级\(level\ 1\)，已知在\(level\ i\)操作一次需花费\(a_i\)，有概率\(p_i\)升级到\(level\ i+1\)，有\(1 - p_i\)掉级到\(x_i(x_i <= i)\)，询问\(q\)次，问你每次从\(l\)升级到\(r\)的花费的期望。

思路：

我们设\(dp[i]\)为从\(1\)升级到\(i\)的期望花费，那么显然有从\(l\)升级到\(r\)的期望花费为\(dp[r] - dp[l]\)。

然后我们可以知道，升级到\(i\)有两种情况：

已经花费了\(dp[i-1]\)必加。从\(i-1\)升级，那么花费\(a_{i-1}\)；掉级到\(x_{i-1}\)再升到\(i\)，那么花费\(a_{i-1} + dp[i]-dp[x_{i-1}]\)，那么可以列出方程：

\[dp[i] = dp[i -1] + p_{i-1}*a_{i-1} + (1-p_{i-1})*(dp[i]-dp[x_{i-1}]+a_{i-1})\]

化简后可得正解。

代码：

#include