题解：CF1693E Outermost Maximums

miao22 · 2025-03-27 12:26:35 · 题解

给一点比较奇怪但我觉得不怎么需要动脑子的做法。

考虑每次对所有的最大值同时操作。此时我们一定是找到严格次大值的位置，对左边按从左到右的顺序做向左的操作，对右边按从右到左的顺序做向右的操作。

注意到对于一个位置，如果它被操作过一次，就永远大于等于左边的所有值或右边的所有值，于是我们就可以想到维护这样的元素。

也即，我们用一个结构维护所有的前缀最大值和后缀最大值，它会是一个单峰的形状。但与其它题解不同的是，我们不要求它是严格的前缀最大值或后缀最大值。

形式化的讲，i 在结构中当且仅当 a_i\geq \max_{0\leq j\leq i} a_j，或 a_i\geq \max_{i\leq j\leq n+1}a_j。

注意到这个结构是只会增加元素的，并且包含了所有的最大值。

然后我们每次对这个结构的最大值进行操作，不妨找到严格次大值，然后对左右各进行操作。

然后就大概是这么个样子。（由于次大值已经让左右两边独立了我们只考虑次大值的左边，右边是对称的）

xx?.|.v.|...|..o

其中：

• | 表示最大值。
• o 表示严格次大值。
• ? 表示非最大值的前缀最大值。
• x 表示我们不在乎的东西，即在 ? 前的元素。
• . 表示我们在乎的东西，即在 ? 后面的元素。它们不是前缀最大值但可能影响本次更新，也可能成为新的前缀最大值。
• v 的定义见后文描述。

我们先找到 ?，然后在 . 中找出第一个 \geq ? 的值。

如果找不到，就把所有的 | 设为 ?，过程结束。

否则把所有 ? 和 v 之间的 | 设为 ?，将 v 加入结构并作为新的 ?。

在两边均完成操作后将 o 加入结构，完事。

另外 o 是新的最大值。

找到最后一个 ? 即找到第一个 | 的前驱，使用线段树二分与 set 即可。

找出第一个 \geq ? 的值需要我们对不在结构中的元素维护一个线段树并进行线段树二分。

如果我们能够找到 o，做法就是简单的，只需维护一个线段树，支持：

• inactive 某点。
• deactive 某点。
• 对 inactive 的点区间加。
• 单点求值。
• 二分找到某个区间第一个 \geq v 的 inactive 点。

容易发现这是可以实现的。

找出 o 稍显困难，你当然可以对线段树额外维护次大值，但这里提供另一个更优雅的做法：

我们其实不需显式求出 o。我们在刚才的过程中对左右同时做，并且不停的选择更小的 ? 进行操作，直到左边的 ? 下标大于等于右边的 ? 下标为止，实际上本题代码的易错部分大概也都在这里。

复杂度分析基本是显然的。非 O(n) 循环的操作均伴随着 O(1) 次有效的 inactive，于是 O(n) 次线段树操作给出 O(n\log n) 的复杂度。

code

跑得飞慢。