Mivik 的神力题解

思路

对位置 $i$ 定义 $nxt_i$ 为右侧第一个满足 $a_{nxt_i}>a_i$ 的位置；若不存在则令 $nxt_i=n+1$。用单调栈可以在线性时间内求出全部 $nxt_i$。

从起点 $l$ 向右观察前缀最大值：在 $[l,nxt_l-1]$ 内最大值恒为 $a_l$；到达 $nxt_l$ 后，新的最大值为 $a_{nxt_l}$。此后完全重复相同结构。因此，一次询问就是沿 $nxt$ 链累加若干完整段，再加最后一个被截断的段。

为快速跳过链上的节点，预处理二进制提升表。再定义

其中哨兵 $n+1$ 的 $S$ 为零。查询时用提升表找到链上最后一个不超过右端点 $r=l+q-1$ 的节点 $p$，答案为

做法

1. 从右向左维护严格递减单调栈，求每个位置右侧第一个严格更大元素。
2. 从右向左计算链后缀贡献 $S_i$。
3. 建立 $nxt$ 关系的二进制提升表。
4. 在线解密每组询问，用提升表找到最后一个位置不超过询问右端点的链节点，并用上式求和。

正确性证明

在区间 $[i,nxt_i-1]$ 内不存在比 $a_i$ 更大的元素，所以从位置 $i$ 开始的所有这些前缀最大值均为 $a_i$。位置 $nxt_i$ 是第一个严格更大的元素，因此从那里开始，前缀最大值的后续变化与从 $nxt_i$ 出发的同类问题完全相同。由此，所有前缀最大值段恰好按 $nxt$ 链排列。

$S_l-S_p$ 正好累加从 $l$ 到 $p$ 之前的全部完整段；最后一段从 $p$ 延伸到询问右端点 $r$，贡献为 $a_p(r-p+1)$。两部分不重不漏，故公式等于题目所求。二进制提升只用于寻找该节点，不改变贡献划分，因此每次输出均正确。按正确答案更新 $lastans$ 后，下一次解密也符合题意。

复杂度

预处理时间为 $O(n\log n)$，每次询问时间为 $O(\log n)$；空间复杂度为 $O(n\log n)$。