浅谈一类在排列上以区间 min / max（值域连续性）为约束条件的子区间相关问题解法

· · 算法·理论

标题可能比较抽象，引入实例就知道是啥意思了。

该系列问题有很多种解法，这里暂时只讲述线段树相关的 3 种。

前置知识：线段树、扫描线。

1. Pudding Monsters / 连号区间数

题意：

给定一个长度为 n\left(1\le n\le 3\times 10^5\right) 的排列 a，求其中满足 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}=r-l 的区间 \left[l,r\right] 的数量。

方法一：

将一段区间 \left[l,r\right] 映射到二维平面上的点 \left(l,r\right)。

用单调栈预处理 premin_{i} / premax_{i} 和 sufmin_{i} / sufmax_{i} 表示位置 i 之前小于 / 大于 a_{i} 最靠后的位置和位置 i 之后小于 / 大于 a_{i} 最靠前的位置。则以 a_{i} 作为区间 min / max 的区间 \left[l,r\right] 一定满足 l\in \left(premin_i / premax_i,i\right] 且 r\in \left[i,sufmin_i / sufmax_i\right)。

不难发现，区间 min / max 相同的所有区间在二维平面上构成一个矩形。使用扫描线从左向右扫，实时维护 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}-r+l ，满足条件的区间该值为 0，该值一定是区间最小值，用线段树维护区间最小值及最小值数量即可。

方法二：

从左向右扫，钦定扫到的位置为区间的右端点。线段树中每个节点维护左端点在该区间的 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}-r+l 最小值及最小值数量。随着右端点右移，区间 min / max 会发生变化，当且仅当单调栈发生变化。每次单调栈发生变化，线段树中都会有一段区间的 min / max 发生变化，只需要使线段树随着单调栈修改即可。

方法三：

因为 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}=r-l，所以满足条件的区间在值域上一定是一个连续段。

依旧是从左向右扫，钦定扫到的端点为右端点，线段树中维护左端点在该区间形成的连续段数量的最小值及最小值数量。

具体地，在右端点 r 右移一位时，a_{r} 会被新加进来。先假定 a_{r} 单独形成一个连续段，在线段树上将 \left[1,r\right] + 1。接着，若 a_{r}-1 的位置 p1 位于 r 之前，则在线段树上将 \left[1,p1\right]-1；若 a_{r}+1 的位置 p2 位于 r 之前，则在线段树上将 \left[1,p2\right]-1。每次统计最小值 =0 的个数即可。

三种方法的时间复杂度均为 O\left(n\log n\right)。

2. Good Subsegments

题意：

给定一个长度为 n\left(1\le n\le 1.2\times 10^5\right) 的排列 a，并给定 q\left(1\le q\le 1.2\times 10^5\right) 次询问，每次询问给出一个区间，求该区间中满足 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}=r-l 的子区间 \left[l,r\right] 的数量。

解法：

上述三种方法依然可以用在该题上。

先把所有询问离线下来，按照右端点大小排序，接下来从左向右扫。对于每个询问 \left[L,R\right]，满足条件的区间 \left[l,r\right] 满足 r \le R。只需要在线段树中再维护一个历史贡献即可。

具体地，在每次右端点右移前，下传一个标记 \text{hst}。在后续修改时，如果某个节点上有 \text{hst}，则先下传 \text{hst}，计入历史贡献后，再下传当前 \text{tag}。

时间复杂度为 O\left(n\log n\right)。

3. Intrinsic Interval

题意：

给定一个长度为 n\left(1\le n\le 10^5\right) 的排列 a，并给定 q\left(1\le q\le 10^5\right) 次询问，每次询问给出一个区间，求包含该区间的满足 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}=r-l 的最短子区间 \left[l,r\right]。

解法：

像上题一样把询问离线下来并按右端点排序。将整个序列从左向右扫，设当前扫到 r。若询问 \left[L,R\right] 未被处理过且其中 R\le r，查找 \le L 的最大的 l 满足 \left[l,r\right] 值域连续，如果有，更新答案。可以把询问放进一个堆里，每次取出 R\le r 的 L 最大的询问即可。如果查询不到区间，跳出循环即可。（因为我们将 L 排序，如果其中一个找不到答案了，则说明 1\sim L 中均不满足条件，比它小的 L 就更加无法找到答案了）

正确性证明：如果上述方法找出来的 \left[l,r\right] 不是最短区间，则必定存在一个区间 \left[tl,tr\right] 满足 l<tl\le L 且 tr > r，它与 \left[l,r\right] 的重合部分为 \left[tl,r\right]，且这段在值域上被分为 \ge 2 段。因为 \left[l,r\right] 值域连续，所以 \left[tl,r\right] 中值域断开的部分均在 \left[l,tl\right] 中，所以不存在值域连续的区间 \left[tl,tr\right]。上述结论与条件矛盾。

上述三种方法均可以用在该题上，需要额外维护一个最小值出现的最靠右的位置。时间复杂度均为 O\left(n\log n\right)。

4. Beautiful Subsequences

题意：

给定一个长度为 n\left(1\le n\le 1.4\times 10^5\right) 的排列 a，求其中满足 \max\limits_{i=l}^{r}a_{i}-\min\limits_{i=l}^{r}a_{i}\le r-l+k\left(0\le k \le 3\right) 的区间 \left[l,r\right] 的数量。

解法：

该条件与连续段个数没有对应关系，维护连续段的方法无法用在该题上。

考虑前两种方式如何实现。

因为 k 较小，所以只需在线段树里维护最小的 k+1 个值及出现次数即可，push_up 需要 O\left(k\log k\right)，时间复杂度 O\left(nk\log n \log k\right)。

5. Two Segments

题意：

给定一个长度为 n\left(1\le n\le 3\times 10^5\right) 的排列 a，求选出两个互不重叠的区间，其组成一个连续的值域的方案数。相同的值域视作相同的方案。

解法：

由于位置不连续，且容易算重，所以考虑值域。问题转化为了在连续的一段值域上，位置组成的连续段 \le 2 的方案数。

使用第一题中的方法三，需要维护最大值和次小值以及它们的数量。

时间复杂度 O\left(n\log n\right)。

因为此题无法得知区间 min / max 的关系，所以方法一和方法二无法使用。