自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:12:55，当前版本为作者最后更新于2019-11-10 23:09:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我并没有神力ww

• 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)$

代码