题目描述

给定一个长度为 $n$ 的序列 $a$，每次询问 $[l,r]$ 内所有连续子区间的区间最小值。

思路

我们分别讲解如何使用离线 / 在线算法解决本题。

离线 / 莫队

使用莫队将问题离线后，我们需要思考如何从 $[l,r-1]$ 的答案推至 $[l,r]$ 的答案。

首先，我们知道一共新增了 $r-l+1$ 个，以 $r$ 为右端点的区间。如果将 $[l,r]$ 中区间最小值的位置记为 $p$，这些区间可以根据是否包含 $p$ 划分为两部分：对于包含 $p$ 的那 $p-l+1$ 个区间，显然它们对答案的贡献都等于 $a[p]$。

对于剩下的 $r-p$ 的区间，我们不妨设一个辅助数组 $f$ 来帮助我们求解。

设 $f[l][r]$ 表示右端点为 $r$，左端点为 $[l,r]$ 中一点的所有区间的答案。和上面的思路一样，我们记 $r$ 之前第一个小于 $a[r]$ 的位置为 $pre$，那么很容易得到这个式子：

$$f[l][r]=f[l][pre]+a[r]\times (r-pre)$$

因此，新增的右端点 $r$ 对答案的贡献为

$$a[p]\times(p-l+1)+f[p+1][r] $$

考虑到 $p \leq pre$，我们可以直接把式子写成

$$a[p] \times(p-l+1)+f[p+1][pre] + a[r]\times(r-pre)$$

我们发现，$f$ 数组的第一维 $l$ 在式子中并没有起到作用，所以我们可以忽略这一维，把 $f$ 写成关于 $l$ 的前缀形式，也就是我们定义新的 $f’$，使得

$\begin{aligned}f'[r]=&\sum_{l=1}^r f[l][r] \ =&f'[pre]+a[r]\times(r-pre)\end{aligned}$

预处理出 $f’$，我们就可以 $\Theta(1)$ 计算 $r$ 对答案的贡献

$a[p] \times(p-l+1)+f[r] – f[p]$

对称地处理 $l$ 对答案的贡献即可。

在线

离线算法给了我们很多启发。

我们预处理出了贼好用的 $f’$ 数组，用来表示固定右端点时，所有区间的答案和；也预处理出了固定左端点时对应的数组。那么我们前缀和一下是不是就能在线回答询问了？我们还是小心地推一下式子。

对于区间 $[l,r]$，我们还是记最小值的出现位置为 $p$。对于跨越 $p$ 的区间，它们对答案的贡献为 $a[p]\times(r-p+1)\times(p-l+1)$。

现在我们考虑区间 $[p+1,r]$ 的答案。由离线做法我们知道，$x$ 为右端点时对答案的贡献为 $f'[x]-f'[p]$。那么我们将 $(r-p)$ 个右端点的答案累加起来，就等于 $f'[p+1]-f'[p]+f'[p+2]-f'[p]+ \cdots f'[r]-f'[p]$。

我们记 $g$ 为 $f’$ 的前缀和，那么上面这个式子就等于 $g[r]-g[p]-f'[p]\times(r-p)$。对于区间 $[l,p-1]$，对称地处理即可。

也就是说，求出 $p$ 之后，我们可以 $\Theta(1)$ 在线回答询问。

代码

离线 / 莫队

在线

附加例题

记长度为 $n$ 的序列 $A$ 的最大前缀和为 $\forall j \in [1,n],\sum_{i=1}^j A_i$ 的最大值。

给定长度为 $n$ 的序列 $a$，每次询问区间 $[l,r]$ 内所有连续子区间的最大前缀和之和。