[Mivik的萌新赛][T3 Mivik的神力] 题解

· · 题解

我并没有神力ww

直接暴力。

时间复杂度 O(m\cdot n^2)

读入时用单调栈记录每一个点后面第一个比他大的数的位置（记为 fa_i ），询问时跳跃统计

时间复杂度 O(n+(m\cdot n\sim m\cdot n^2))

出题人：是我少出了单调递增的数据点卡你们

观察到这个序列是不变的，因此我们预先倍增处理一个点往后“跳跃” 2^k 次能跳跃到哪里和“跳跃”的贡献

时间复杂度 O(n+m\cdot\log n)

我们来观察一个区间。我们从这个区间的左端点开始“跳跃”统计，我们将在哪一个点结束呢？

没错。我们将会在这个区间最左侧最大值的位置结束。我们可以用一个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)

代码