「hyOI2020」henry_y 的数列题解及一种分块优化最小值左移的想法

嘉然小姐的狗 · 2020-06-10 07:41:46 · 个人记录

摘要

本文从经典的区间加一次系数非负的一次函数及维护区间最值问题开始，探究一种利用分块优化最小值下标左移的思路而不使用凸壳算法 O((n + q) \sqrt n) 解决此问题的方式，并扩展到使用分块及二维凸壳 O((n + q) \sqrt n) 解决区间加二次系数及一次系数均非负的二次函数及维护区间最值问题。

记录符号

区间加 k \geq 0 的一次函数及维护区间最值问题

维护一个长度为 n 的正整数序列 \{A_n\}，维护 q 个操作，操作有两种：

1 l r k b：\forall l \leq i \leq r, i \in \mathbb{N}，令 A_i \leftarrow A_i + ki + b；
2 l r：输出 \min_{l \leq i \leq r} \{A_i\} 的值。

保证 k \geq 0。

解法 1：分块维护二维凸壳

这是本题的经典解法。

对序列分块，块大小为 O(\sqrt n)。对每个元素 A_i，把更改后的 A_i 视为一个以 k 为变量的一次函数 f_i(k) = i \times k + A_i。对于每个块，我们维护两个修改标记 \sum k 和 \sum b，那么求这个块内元素的最大值，相当于求

\min_i\{i \times \left(\sum k \right) + \left( \sum b \right) \} = \min_i\{i \times \sum k \} + \sum b = \min_i\{f_i(\sum k)\} + \sum b

相当于求块内 O(\sqrt n) 个一次函数在 x = \sum k 处的最小值。预处理出块内的上凸壳，就可二分求出最小值。

注意到

函数斜率 i 递增。

所以重构块和维护询问时都可以使用单调队列，避免二分增加 O(\log n) 的开销。

时间复杂度：O((n + q) \sqrt n)。

解法 2：分块优化最小值左移

同样考虑分块，块大小为 O(\sqrt n)。对每个块处理：

块中最小值所在的下标（如果有多个最小值，取下标最小的）\text{minpos}；
令整个块最值改变所需的最少的 \sum k 值 \text{limk}。

考虑求解 \text{limk}。设块中 j < \text{minpos}，若更改后 A_j' 小于 A_\text{minpos}'，那么有

\begin{aligned} A_j + jk &< A_\text{minpos} + \text{minpos}k \\ A_j - A_\text{minpos} &< (\text{minpos} - j)k \\ \lfloor \frac {A_j - A_\text{minpos}}{\text{minpos} - j} \rfloor &< k \\ \end{aligned}

所以

\text{limk} = \min_{\text{bl} \leq j < \text{minpos}} \{\lfloor \frac {A_j - A_\text{minpos}}{\text{minpos} - j} \rfloor\} + 1

对每个块记录两个懒惰标记（Lazy tag）\text{madd}, \text{msup}，表示这个块内的元素 A_i' 应当为 A_i + \text{madd} + i \times \text{msup}。当 \text{msup} \geq \text{limk} 时，O(\sqrt n) 重构此块。

时间复杂度：O((n + q) \sqrt n)。

复杂度证明

设块的势能为它在仅受整体影响（即不出现边角情况，不出现局部影响）下能被重构的最多次数。

首先，单个块的势能不超过 O(\sqrt n)。若一个块仅受整体影响，则这个块在重构时，最小值的下标必定会向前移动。由于块大小为 O(\sqrt n)，因此重构次数，即势能也不超过 O(\sqrt n)。所有块的初始势能总和不超过 O(\sqrt n) \times O(\sqrt n) = O(n)。

其次，若块内 A_j' 可能成为最小值，则有 j = \text{bl} 或 A_{j - 1} \geq A_j（反之不一定成立）。一个块的势能大小不大于满足 A_{j - 1} \geq A_j 的 j 的个数。

考虑修改操作的影响。

对修改区间外：无影响。
对处于修改边界上的元素：由于修改边界最多只有 O(1) 个，因此势能增加不超过 O(1)。
对处于修改区间内的元素：注意到 A_{j - 1} 的增加量不大于 A_j 的增加量，因此 A_{j - 1} < A_j 的相对大小不变，而 A_{j - 1} \geq A_j 可能在修改后变为 A_{j - 1}' < A_j'。此时满足条件的 j 的数量不增多，势能不增大。虽然这可能引起块的重构，但重构最多仅 O(1) 次，而如果重构则势能减少至少 O(1)，所以对总复杂度没有影响。

可见单次修改操作均摊增加势能为 O(1)。

考虑询问操作的影响。询问操作不改变元素的实际值，只下放标记，因此势能不变。

所以，所有操作增加的势能不超过 O(q)。

综上所述，可能的总重构次数，即总势能不超过 O(n + q)，乘上单次重构的复杂度 O(\sqrt n)，总时间复杂度为 O((n + q) \sqrt n)。

区间加一次函数及维护区间最值问题

维护一个长度为 n 的正整数序列 \{A_n\}，维护 q 个操作，操作有两种：

1 l r k b：\forall l \leq i \leq r, i \in \mathbb{N}，令 A_i \leftarrow A_i + ki + b；
2 l r：输出 \min_{l \leq i \leq r} \{A_i\} 的值。

解法：分块维护二维凸壳

采用和区间加 k \geq 0 的一次函数及维护区间最值问题类似的做法。唯一不同的是，由于 k 可正可负，因此 \sum k 不一定单调，询问时只能使用二分（不过重构仍然是 O(\sqrt n) 的）。

时间复杂度：O((n + q\log n)\sqrt n)。

伪解法：分块优化最小值左移

可以使用类似的思路吗？

类似地，我们维护令整个块最小值改变所需绝对值最小的 k 值的上界和下界。

不幸地，这一方法最坏复杂度为 O(nq)。下面给出了一个构造极端数据的方式。

初始时，令 A_i = n - i。此时 \{A_n\} 单调递减。
令全局增加 2i。此时 \{A_n\} 变为单调递增，所有块被重构，复杂度为 O(\sqrt n) = O(\sqrt n) = O(n)。
为了防止不查询就不重构块的做法，查询全局最小值。
令全局减少 2i。此时 \{A_n\} 又变为单调递减，所有块又被重构，复杂度为 O(\sqrt n) = O(\sqrt n) = O(n)。此时 \{A_n\} 回到初始状态。
转到第 2 步，重复。

以这样的方式，此算法会在 O(1) 个操作上花费 O(n) 的时间计算。重复此构造方式便可使该算法运行时间为 O(nq)。

特别地，该算法在部分随机数据下表现较良好（可见 Moonoshawott 在洛谷 P4192 旅行规划的提交记录）。但仍然要指出的是，选手应尽可能使用正确的算法，否则可能会因随机数据的常数或构造数据方式的不同而表现不优。

「hyOI2020」henry_y 的数列（区间加 a, b \geq 0 的二次函数及维护区间最值问题）

维护一个长度为 n 的正整数序列 \{A_n\}，维护 q 个操作，操作有两种：

1 l r a b c：\forall l \leq i \leq r, i \in \mathbb{N}，令 A_i \leftarrow A_i + ai^2 + bi + c；
2 l r：输出 \min_{l \leq i \leq r} \{A_i\} 的值。

保证 a, b \geq 0。

解法 1（？）：分块维护三维凸壳

采用和区间加 k \geq 0 的一次函数及维护区间最值问题类似的方式，询问问题就变成了一个维护二元一次函数 f_i(a, b) = ai^2 + bi + A_i 最小值的问题。

由于笔者学识浅薄，此处不对该解法的正确与否妄下断语。如果有选手可以以优秀的复杂度实现这个算法，可以在题目讨论区里留言。

解法 2：分块维护二维凸壳优化最小值左移

回顾一下我们刚才的所有证明。不难发现，维护这个只需要满足以下条件：

可以在 O(\sqrt n) 时间内完成对一个块的重构
可以在均摊 O(1) 时间内判断一个块的最小值的位置是否必须发生改变
可以在 O(1) 时间内维护修改标记并在重构时下放
对于修改区间内的相邻元素，有 \Delta A_i \leq \Delta A_{i + 1}（即 A_i 增加的值不大于 A_{i + 1} 增加的值）

不难发现区间加 a, b \geq 0 的二次函数满足条件 3, 4，问题转化为在满足条件 1 的前提下解决条件 2。

设标记 k_0, k_1, k_2 表示修改 A_i' = A_i + k_0 + k_1i + k_2i^2。对于 j < \text{minpos}, A_j \geq A_\text{minpos}，修改后 A_j' < A_\text{minpos}' 的充要条件是

\begin{aligned} A_j + k_2j^2 + k_1j &< A_\text{minpos} + k_2\text{minpos}^2 + k_1\text{minpos} \\ (A_j - A_\text{minpos}) + k_2(j^2 - \text{minpos}^2) + k_1(j - \text{minpos}) &< 0 \\ \frac {A_j - A_\text{minpos}}{j - \text{minpos}} + k_2(j + \text{minpos}) + k_1 &> 0 \\ k_1 &> (-\text{minpos} - j)k_2 + \frac {A_j - A_\text{minpos}}{\text{minpos} - j}\\ \end{aligned}

把不等式的右半部视作关于 k_2 的一次函数 f_j(k_2) = (-\text{minpos} - j)k_2 + \frac {A_j - A_\text{minpos}}{\text{minpos} - j}。对每个块，维护其 O(\sqrt n) 个一次函数 f_j(k_2) 的最小值（上凸壳），并在每次块修改时，判断

k_1 > \min_j\{f_j(k_2)\}

若条件满足，则重构此块。至于复杂度：

综上，我们可以用分块维护上凸壳的方法解决这个问题。

时间复杂度：O((n + q) \sqrt n)。

伪解法：分块钦定二维凸壳优化最小值左移

此解法由 @hjw 提出，在此感谢 hjw 的协助验题、提出算法和提供构造数据的方式。

同样分块，并把每个元素视为二维平面上的点 (i, A_i)，求出其在保证凸壳上 A_i 递减前提下的下凸壳，并记录当前最小值下标 \text{minpos}（不难证明 \text{minpos} 一定在下凸壳上）。

对于每次询问，设 j 为下凸壳上 \text{minpos} 的前一个元素，若 A_j' \leq A'_\text{minpos}，则令 \text{minpos} 更新为 j。重复此步骤直到 \text{minpos} 为下凸壳上的左端点或 A_j' > A'_\text{minpos}。

尽管这个算法看起来不太正确，但它仍通过了几乎所有的随机数据和部分构造数据。笔者试着思考了三天，也没能找出卡掉此算法的构造方式。

要证明这个算法的正确性，只需要证明:

不在下凸壳上的点不会成为唯一的最小值（优越性）。
设 i < j < k 在下凸壳上。对于任意时刻，若 a_i' < a_j'，那么一定有 a_j' < a_k'（传递性）。

传递性是正确的，可以通过简单的反证法证明。因此，若最小值在下凸壳上，那么这个算法一定能得出正确结果。几乎所有的随机数据都满足最小值在下凸壳上，因此得出的结果是正确的。

然而优越性是错误的，可以构造出反例。@hjw 给出了一种构造反例的方式：

决定 1 \leq i < j < k，其中 j - i \leq k - j。
决定 \alpha, C，使得区间加上 \alpha i^2 + C。
计算 A_i = \alpha(k^2 - i^2) + C, A_j = \alpha(k^2 - j^2) - 1 + C, A_k = C。

此时 (i, A_i), (j, A_j), (k, A_k) 在区间加 \alpha i^2 + C 的情况下，可以卡掉此算法，即

利用此构造方法即可构造出卡掉此算法的数据。

时间复杂度：O((n + q) \sqrt n)。

后记

为了叙述简洁易懂，本文中仅描述了维护最小值的方法。维护最大值的方法是类似的，且可以以相同的复杂度同时维护最大值与最小值。

本文描述的分块优化最小值左移的思路，对于区间加非常数项系数均非负的 k 次函数及维护区间最值的问题，可以将其转化为维护 k - 1 元一次函数最小值或最大值的问题。也就是说，如果有利用分块维护三维凸壳解决区间加二次函数的方式，那么也有可能可以利用类似的做法解决区间加三次函数的问题。