[Mivik的萌新赛][T3 Mivik的神力] 题解
一个序列，多组询问，每次询问给出 $l$ 和 $q$，问：
$$
\sum_{i=l}^{l+q-1}\max_{l\le j\le i}a_j
$$强制在线。
$1\le n,m\le 5\cdot 10^5$
思路
我并没有神力
- 20 pts.
直接暴力。
时间复杂度 $O(m\cdot n^2)$
- 90 pts.
读入时用单调栈记录每一个点后面第一个比他大的数的位置（记为 $fa_i$ ），询问时跳跃统计
时间复杂度 $O(n+(m\cdot n\sim m\cdot n^2))$
出题人：是我少出了单调递增的数据点卡你们
- 90 pts. $PLUS$
观察到这个序列是不变的，因此我们预先倍增处理一个点往后“跳跃” $2^k$ 次能跳跃到哪里和“跳跃”的贡献
时间复杂度 $O(n+m\cdot\log n)$
- 100 pts.
我们来观察一个区间。我们从这个区间的左端点开始“跳跃”统计，我们将在哪一个点结束呢？
没错。我们将会在这个区间最左侧最大值的位置结束。我们可以用一个ST表来维护区间最大值的位置
然后我们来观察我们这个“跳跃”的路径，由于每一个点有且只有一个“跳跃”的目标，因此不能看出这是一个树形结构
综上所述，我们现在知道了树上的起始点和结束点，那么这个题就被转化为树上求两点之间距离的板子题了
又由于本题的特殊情况，我们的结束点必定是起始点的祖先，因此我们仅仅需要一个 $dis$ 数组来存储每一个点到根节点（ 根节点是 $n+1$，因为原序列最大值默认的 $fa$ 是 $n+1$ ）的距离即可
举个例子
我们现在有一个序列 $1,1,4,5,1,4$ ，那么我们可以得到它对应的 $fa$ 数组为 $3,3,4,7,6,7$
我们把每一个点的 $fa$ 作为它在树上的父亲，就可以得到下面的树
这是假如我们想要查询 $[1,5]$ 这个区间的答案，我们可以首先查询到 $[1,5]$ 这个区间的最大值是在第4位，因此答案最终就是要从1号点跳到4号点路上所有的权值，再加上4号点到5号点额外的贡献
时间复杂度 $O(n\cdot\log n+m)$
代码
[Mivik的萌新赛][T3 Mivik的神力] 题解
