P14665 bonus 细谈

· · 算法·理论

原题

这里提出对于 1 \le n,a_{i} \le 2 \times 10^{7},0 \le m \le 10^{18} 的做法。

关键观察

区间加/减可以转换成环上补集的区间减/加。

证明：考虑数字之间的相对大小，如果一段被削减了，以它为参考系，其它段就抬升了。这是等价的。

在这里，我们将区间减转化成环上区间加。

那么自然，区间加不能涉及到最大值，否则这一次是无意义的。如果某一次操作涉及了最大值，我们完全可以让它缩短一点“吐出”最大值，因为这样得到的结果一定不劣（如果包含最大值，结果就会是 +1/不变，如果不包含，则会是不变/-1）。

既然如此，我们的目标就变为：在 m 次操作里尽量增大最小值。

并且每次操作也被最大值天然隔断了，此时就可以以任意一个最大值为断点断环成链，换回序列问题，并且区间减一的操作已经被转化掉了。

最大值记作 M，当前最小值记作 P。

贪心构建

现在考虑 \max - \min - m 得到的答案为什么不对。

它假定了：“每次操作必然能将全体最大/小值进行一次削减/抬升”，而这在最大最小值交替出现时就出现了错误——无法一次性在不影响另一个最值的前提下整体修改当前最值。

一组数据：

4 1
1 2 1 2

答案是 1，因为在试图一口气修改某个最值的时候，另一个最值必然受到了等量的改变；而这就导致了极差不变。

如何改正原思路呢？那我们可以考虑不去假定“每次操作必然能将全体最小值进行一次抬升”，而是去想：

“至少需要多少次操作才能让全体最小值进行一次抬升？”

有了！维护这样的操作段即可。不过我们不关心到底是哪些段，因此只用考虑维护段数。

性质挖掘

先直接将值相同的连续段挑出来，它们可以当成一个单点做，缩一块即可。

根据结论以及一又点点观察，我们又知道：

每次操作肯定提升了一个不包含最大值且包含最小值的极长段。

这是很显然的一点，既然不涉及最大值，那么自然越长越好。

长什么样子？考虑一个已经被转换后的序列：

xo---x--x-o-o--x-xo---

x 表示最大值，o 表示最小值，- 表示中间值。

那么操作段 n，就长这样：

xnnnnx--xnnnnnnx-xnnnn

共 3 段。

那么究竟如何维护呢？接下来将会涉及许多转化，跟上咯！

我们需要解决两个问题：

  1. 如何得到新最小值的位置，以及它对段数的影响？
  2. 如何得到新最大值的位置，以及它对段数的影响？

问题 1

为什么会有这个问题？考虑当我们将现有最小值从 h 变为 h+1 时，原本就是 h+1 的且没有被操作的值自然就变成新的最小值啦！

例子：

xnnnnx--xnnnnnnx-xnnnn

变为

xnnnnxo-xnnnnnnx-xnnnn

变为

xnnnnxnnxnnnnnnx-xnnnn

这样就会增加段数。

原最小值肯定还是新的最小值，因此不用考虑删除。

我们发现一个性质：每当多出一个最小值，其带来的影响就是一连串的，它会导致从它开始，向左右扩展，直到碰到边界或者最大值为止的位置集合全变成操作段的一部分。

我们维护一个 vis[] 数组，看看某个新的最小值是否导致新段的产生即可。

问题 2

为什么会有这个问题？考虑我们操作某段时，中间可能会有“间谍”——等于 M-1 的值！操作完成后，它就变成了最大值，导致操作段被隔断，一分为二。

我们需要迅速挑出这些间谍。

从头来看，每个值从原值加到 M 需要一定的过程。逆向思考，也就是最大值在相对它们“减小”。

我们可以维护一个 \text{deadline}（简称为 d）。具体来说，如果某个位置的“特征值”等于 d，那么它现在就是最大值了。每轮操作后，d 减一，表示这些值更大了一点，d 是一个相对概念。

每当我们更新操作段时，就将那些新加入的位置加入到 d 的桶 dl 里，让 d 慢慢接近它们。

如何维护？对于初始被最小值加入的位置来说，它们的特征值自然是这个位置的原值 a。

在枚举到 h 时加入的位置呢？由于它们比初始加入的要晚 h-P 时刻，那么它们的特征值自然是 a-(h-P)，表示 d 需要更长的时间才能到达这些位置。

不会出现负特征值，因为所有值迟早都会变成 M。

小示例

3 1 2 1 3 2 3

操作段为 [2,4]，仅一个，进行操作后：

3 2 3 2 3 2 3

发现：位置 7 变成了新的最小值，位置 3 变成了新的最大值，操作段数变成了 3。

实现要点

我们将连续段挑出来后，按照值建桶。

将初始最小值扩展一遍，d 初始等于 M。

从小到大枚举最小值 h，按照上述方式维护操作段数。

顺序为：

  1. 先 check 旧值能否提升得到这个新值 h（m \ge cnt?），如果不能就退出，如果能，就将 m 减去 cnt，d 减一，并进入 2；
  2. 然后扫一遍 h 的值域桶，看这些最小值是否已经被覆盖过，如果没有覆盖过，则进入 3；随后扫一遍 d 的桶 dl_{d}，对于每个在这里被扫到的位置，进入 4；
  3. 向左向右扩展，直到撞到已经变成最大值的位置为止。对于每个新加入的位置 pos，将其加入 dl_{a_{pos}-(h-P)}；
  4. 看看其左右是否有已经变为最大值的标记（用一个布尔数组存即可），然后标记当前位置。如果左右都没有最大值，说明这是一个存在于操作段内部的隔断，cnt+1；否则，如果恰好有一个最大值，说明这在边界，cnt 不变；否则，说明我们把一个最小值变成了最大值，程序就该结束了。

对于步骤 2，这两小步的先后顺序可以颠倒。因为如果新最小值碰到新最大值，说明这个新最小值本身就不会扩展。因为“新最大值”隐含了一个前提：这个位置是被操作变成最大值的。说明这个新最小值本身也一定被同一个操作段所包含，不存在顺序问题。

每个位置最多被扩展一次、标记最大值一次、压入 dl 桶一次，因此为 O(n)。扫一遍值域是独立的 O(V)。

总时间复杂度 O(n + V)。如果 a 较大，就需要离散化 O(n \lg V) 处理，不过基数排序常数很小，能支持 1 \le a \le 10^{18}。

这样应该有蓝了吧