P5648 Mivik的神力

P5648 Mivik的神力

卡常倍增 或 树状结构维护

想了好久也没思路。

首先很容易发现维护静态区间 max 是很容易的（st表），但是仍然不能快速维护前缀max和。

考虑前缀max 的性质。首先前缀max 的值是单调递增的，对于前缀max 序列，可以将其分成若干个内部相等的段。也就是对于每个数 \(a_i\)，都有一个向右的固定的管辖范围，即到第一个比它大的数（单调栈维护）。

如果考虑优美一点的暴力，我们可以按每一段处理（每一段权值固定)，最优复杂度当然是只有一段区间是，复杂度为 \(O(1)\)。但是遇到单调递增的区间，就会被卡到 \(O(n)\)。

瓶颈在于每一次我们都要跳到下一个新的段，段数太多，不能一个一个跳。那我们的思路就有了——倍增。

我们考虑 \(f_{i,j}\) 表示从 \(i\) 位置跳 \(2^j\) 段的答案。设 \(nxt_{i,j}\) 表示从 \(i\) 位置跳 \(2^j\) 段后的位置，那么有：

\(nxt_{i,j}=nxt_{nxt_{i,j-1},j-1}\)

\(f_{i,j}=f_{i,j-1}+f_{nxt_{i,j-1},j-1}\)

第二个式子成立的原因是，从 \(i\) 一直跳只会有一种跳法，并且每段可以直接相加。

统计答案时从大到小枚举 \(j\)，能加就加即可。这种倍增做法的复杂度显然是 \(O(n\log n+m\log n)\)，可能需要一些卡常才能过。

考虑更优的做法，我们发现对于每个 \(i\)，从 \(i\) 一直跳只会有一种跳法，最后一跳相当于跳到 \(n+1\)。我们发现这样构成了一个树状结构，有 \(n\) 条链，根节点是 \(n+1\)。对于每个询问区间 \([l,r]\)，\(\rm maxn\) 的位置为 \(p\)。那么 \(l\) 到 \(p\) 就对应树上的一条链，并且 \(p\) 为 \(\rm lca\)。 于是 \([l,p]\) 的求解就变成了树上链求和。

转化完后，维护每个节点到根节点的前缀和 \(sum_{i}\)。答案即为 \(sum_i-sum_p+calc(p,r)\)。\(calc(p,r)\) 即为 \(\rm maxn\) \(\times \ (r-p+1)\)。

复杂度为 \(O(n\log n+m)\)，稳。

总结就是优化跳跃的题目经常会和倍增相关，如果跳跃路径固定，路径会构成树状结构，达到转化。