随笔题解 Pb. 7

Codeforces Round 911 (Div. 2) F. Local Deletions

什么？我连 Div. 2 F 都写出来了？

以下是前置知识。

对于一个序列 $a_1, a_2, \dots, a_n$，定义 $a_i$ 是一个局部最小值当且仅当

$$(i = 1 \vee a_i \lt a_{i - 1}) \wedge (i = n \vee a_i \lt a_{i + 1})$$

定义 $a_i$ 是一个局部最大值当且仅当

$$(i = 1 \vee a_i \gt a_{i - 1}) \wedge (i = n \vee a_i \gt a_{i + 1})$$

设 $x$ 是一个序列，其中的数字互不相同。定义 操作 $f_1(x)$ 表示保留 $x$ 中的所有局部最小值，并将这些数字按照原顺序拼接起来；$f_2(x)$ 类似，只不过是保留局部最大值。操作不给出返回值，而是会直接修改 $x$。

定义 函数 $f(x)$ 表示在 $x$ 上按照 $f_1, f_2, f_1, f_2, \dots$ 的顺序应用上述两种操作，直到 $x$ 中只剩下一个数字。那个数字就是 $f(x)$ 的值。

比如说，考虑 $[1, 3, 2]$。应用 $f_1$ 得到 $[1, 2]$，再应用 $f_2$ 得到 $[2]$。于是 $f([1, 3, 2]) = 2$。

以下是正文。

给出一个长度为 $n$ 的排列 $a_1, a_2, \dots, a_n$。$m$ 次询问，每次给出一个区间 $[l, r]$，试求 $f([a_l, a_{l + 1}, \dots, a_r])$。

$1 \leqslant n, m \leqslant 10^5$。

$\mathtt{3s/256MiB}$。

首先我们可以（或感性或理性地）注意到以下几点：

1. 大部分 $[l, r]$ 区间上的局部最值同时也是整个序列的局部最值
2. 只有 $[l, r]$ 最靠两侧的两个数字可能不满足上一条
3. 每次应用 $f_1$ 或 $f_2$，都会使得序列的长度至少减半

我们可以预处理出整个序列应用 $k$ 次操作之后会变成什么样，记为 $A_k$。

对于依次针对 $[l, r]$ 的询问，应用 $k$ 次操作之后得到的序列，它的核心部分一定是 $A_k$ 的一个子区间。考虑到最靠两侧的两个数字可能会出问题，我们可以直接把它们拆成散点，然后对于所有拆出来的散点暴力求解。

这样，最多 $\log n$ 次模拟之后，核心区间就会完全消失，剩下最多 $2 \log n$ 个散点同样暴力求解。

时间复杂度的一个很松的上界是 $O(n \log n + m \log^2 n)$。但是基本跑不满，在实际数据上的表现非常优秀。

看了一眼官方题解，看到还提到了一个性质：左右两边的散点数量各自不会超过一个。

这十分明显：每次核心区间分裂出散点之后，这个新的散点和之前旧的散点必定只能保留一个。

这样一看的话时间复杂度应该在 $\Theta((n + m) \log n)$ 左右。