题目描述

给定一个长度为 $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]$ 内所有连续子区间的最大前缀和之和。

Leave a Reply to kal0rona

  1. kal0rona
    Mar 18, 2019

    莫队转移的思路很优秀啊…

    Reply