[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的神力] 题解

https://mivik.gitee.io/2019/solution/miviknewbie-t3/

作者

Mivik

发布于

2019-11-10

更新于

2021-05-31

许可协议

评论