星际穿越
zoxx
·
·
个人记录
星际穿越
题意
有n个节点，分别从1到n编号，给定一个数组l_i,对于每个非1节点都有连向[l_i,i-1]的长度为1的无向边，给出q组询问l_i,r_i,x_i(l_i<r_i<x_i)问x_i到[l_i,r_i]中任意一点的期望最短距离，即
\frac {\sum \limits _{j=l_i}^{r_i}dis(x_i,j)}{r_i-l_i+1}
#### 题解
首先我们可以得到一个结论，最多只会向右跳一次。为什么呢？向右跳的意义就是能想做跳的更远(注意$l_i<r_i<x_i$),那么如果我们向右跳两次能跳到一个，那么向左跳一次也能跳到，否则来到这样一个“偏远”的点就根本没有意义
那么接下来我们应该怎么跳呢？我们可以尽量向左跳，如果在哪一步跳过了应跳到的点，那么说明上一步可以”撤回“，肯定也能用最少的步数跳到目的地。那么除了第一步只能最远跳到$l[i]$以外，我们都跳$min_{x=i}^{n}\{ l[i]\}$，这显然是可行的，如果已经跳到就可以了，先处理出$dis(i,j)$,再用前缀和进行优化，这样就可以得到一个$O(n^2+m)$的暴力,已经可以得到较高的分数。
我们再来考虑优化这样一个暴力，由于每一次的决策都是固定的，我们可以选择使用倍增来进行优化。
但由于求的是$\sum \limits _{j=l_i}^{r_i}dis(x_i,j)$,所以直接倍增求解是过不了的，但是我们可以 用前缀和进行优化，将其变成$\sum \limits _{j=x_i}^{l_i}dis(x_i,j)-\sum \limits _{j=x_i}^{r_{i+1}}dis(x_i,j)$,然后分别计算。我们计$f[i][j]$为从$j$出发向左跳$2^i$能跳到哪里，记$g[i][j]$为$\sum \limits _{k=j}^{f[i][j]}dis(k,j)$,那就可以在将其预处理出来，对每一个询问倍增差分进行计算即可。有一点需要注意，倍增计算的第一步需要特判。