题解 P4118 【[Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?】

· · 题解

update：看这个题好像不咋换数据了于是确认代码能过之后再最后改一遍。。。。

目前看来最大点是 #21 1.16s。

别再改数据了吧，这代码我实在不想再卡常了/dk，这题解我也不想再更新了/dk

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉要一直幸福下去哦~

代码长达 12K，喜提最长解。wtcl

希望这道题不会让各位对珂学的热爱丧失殆尽。

臭名昭著的研究珂学的最佳方式 举世闻名的「深潜循藏第六分块」。

0 前置知识

  1. SPOJ GSS 系列
    • 最大子段和的做法，写了你就知道是啥了。
  2. 凸包、闵可夫斯基和、Jarvis
    • 不会的话可以去看一下二维凸包模板里面 ShineEternal 神仙的题解。
  3. 线段树、分块
    • 如果这个还不会那就不要做 Ynoi 了吧
  4. 基数排序
    • 这个在 v5 里面不需要，但是现在这题是 v6，所以一个高速的基数排序是很重要的~

好了，确认你都会了？

Then~start!

1 弱化

如果问题弱化为全局加区间最大子段和，这道题怎么做？

如果不带修，那么就是一个经典问题，可以维护一棵线段树，每一个节点上面维护区间和、区间最大后缀和、区间最大前缀和、区间最大子段和，合并的时候直接分类讨论即可。

然后如果加上全局加，我们还是考虑如何维护上面的四个信息。

首先区间和直接做就可以。

区间前缀和可以维护一个凸函数 f(x) 表示长度为 x 的前缀和。

后缀和同理，记这个函数为 g(x)。

全局加 d 然后提取最大的时候是最大化 f(x)+dx（g(x)+dx），显然可以凸包二分。

然后我们去考虑如何求区间最大子段和。

还是维护凸包的思路，维护一个凸函数 h(x)，表示长度恰好为 x 的子段和最大为多少。

然而这个东西是没法直接求的……

换一个思路，我们取在线段树上两个子节点的 g_L(x) 和 f_R(y)，然后有关系式 h(x+y)=g_L(x)+f_R(y)。

所以这个 h 实际上就是 g_L 和 f_R 的闵可夫斯基和再对 h_L 和 h_R 取 \max。

又因为我们的 x 是区间长度，即定义域大小是线性的，那么凸包长度就也是线性的。

所以我们对于一个大小为 s 的节点可以 O(s) 求出这个点上面的所有凸包。

既然这样，我们就可以 O(n\log n) 建出线段树。

提取答案的时候，每一个节点凸包二分，共 \log n 个节点，故每次询问的复杂度为 O(\log^2 n)。

注意：P5073 的解法与此稍有不同，因为 P5073 可以也需要通过离线转换为只加正数从而达到均摊单次询问 O(\log n)，但是这题并不完全需要，后面会讲到。

我就是因为受 P5073 的思路制约导致在这题上面卡了好几天……

2 本题高复杂度解法

我们对这个序列分块，在每一块上面建 1 中所说的线段树，每次整体修改可以直接做，零散修改重构线段树，整体查询和零散查询都查询线段树。

这样如果块长为 s，整体修改 O(1)，零散修改 O(s\log s)，整体查询 O(\log s)，零散查询 O(\log^2 s)，可以得到一个复杂度为 O(n\sqrt n\log n) 的解法。

灵魂拷问：能 过 吗？

显然是不能的。

于是就有了——

3 本题低复杂度解法

我们发现复杂度有两个瓶颈：一是零散修改，二是整体查询。分开讨论怎么优化。

3.1 零散修改优化

真的有必要重构整棵线段树吗？

不要忘了：

  1. 线段树的子树还是线段树
  2. 这里的线段树支持整体加，不支持区间加

所以我们可以在零散修改的时候在终止节点上面打标记，非终止节点线性重构。

对于标记的下放，我们可以这样处理：我们在线段树上搞一个节点整体加的标记，这个是正常下放的；然后再在凸包上面维护一个凸包整体加的标记，这个标记是只叠加不下放的。取凸包内节点的时候考虑叠加的正比例函数对点的位置的影响即可。

因为每一层非终止节点的数量是 O(1) 的，所以等比数列求和一下零散修改就变成 O(s) 的了，但是常数比较大。

你可能会问，这里的线段树不是只支持加正数的吗？如果加负数怎么做呢？

事实是：这个线段树支持加负数。 因为 P5073 限制了我们的复杂度到 O(\log n)，而这题并没有。 所以采用二分的方式提取答案，是可以支持加负数的。

所以零散修改的复杂度就下降到了线性。

3.2 整体查询优化

首先我们引入一个科技：逐块处理。

这个科技适用于修改和查询都按块独立且允许离线的问题。

对于这个问题，区间加肯定是按块独立的没话说，最大子段和我们也有办法快速合并，所以就可以逐块处理。

而逐块处理就是离线每一个输入的操作对这个块的操作，然后依次算一遍第一块的所有操作，算一遍第二块的所有操作……

这样的好处在于，如果我们的第 i 次操作和第 j 次操作修改了这个块 (i<j)，那么此时这两个操作之间的所有操作都可以 随意改变顺序，而传统分块是做不到这一点的。

现在来看如何使用这个科技解决这题。

我们发现，整体查询一定是提取线段树根上面那个凸包，而因为整体修改是用一个全局 tag 保存，所以 根上一定是没有标记的。

既然这样，我们就可以把所有查询按照查询时整体加 tag 的值升序排序，然后转换成整体加只加正数。（这里就是逐块处理的应用——改变询问顺序。）

这样在根上面提取答案的时候可以类似 P5073 那样搞个指针往右爬，从而 O(s) 处理所有询问。零散修改重构凸包的时候，直接把指针重置为 0 即可。

这样处理询问的复杂度就是 O(ms)。

证明：

我们定义一个块的势能 E 为根上面的指针距离块右端点的距离。

那么显然初始的势能 \sum E=O(n)。

那么我们每次零散操作会把指针置回 0，导致增加 O(s) 的势能。

而每一次操作只会导致 O(1) 个块被零散操作。

故总零散操作的数量是 O(m) 量级的。

所以总势能是 O(ms) 的。

又因为每次爬指针的时候是 O(1) 时间减少 O(1) 势能，故总时间最大为 O(ms)。

Q.E.D.

但是还有一个问题，排序的复杂度仍然是 O(ms\log m)。

所以换成基数排序，这样就实实在在地优化到 O(ms) 了。

那么，现在得到了一个零散修改 O(s)，零散查询 O(\log^2s)（当然你也可以用暴力扫的方式来 O(s)，不过我觉得这样比较方便），整体修改 O(1)，整体查询均摊 O(1)（因为是 O(ms) 时间， O(ms) 次查询）的算法。

取 s=\sqrt n，得此时算法的复杂度为 O(m\sqrt n)。

芜湖，起飞！

4 常数优化

但是 lxl 显然不会让你就这样愉快地过掉这道题……

于是我们开始卡常：

4.1 优化 1

我们发现，\log_{10}v 和 \log_2n 的差距不是很大，除 10 又会有很大的常数。所以基数排序的基数取 2048，这样可以位运算，\log_{2048}v 也很小，速度就会快不少。

4.2 优化 2

我们发现，每次排序的时候用 2048 个 vector 来保存桶会导致动态分配内存占用巨大的时间。

然而我们在排整数序列的时候，是用 2048 个 int 来保存每一个数的出现次数，然后再放回到数组里面，这样就避免了分配内存的压力。

这里的应用是单关键字排序结构体，所以如果我们能把结构体的下标强行附加到全局 tag 上，一切问题就都解决了。

显然我们可以做到这一点，我们把下标乘上 2^{35} 然后加到全局 tag 上面，排序仍然只排 3 次。这样因为排序只会考虑到 33 位以下的部分，下标就不会参与排序。

于是我们就得到了按照关键字排好序的下标数组，对应回去即可。全过程中可以完全避免动态分配内存，就会有很大的速度提升。

而且在结合了优化 2 之后，可以将基数排序的基数改为 256，由于缓存的影响，速度会有极大的提升。

4.3 优化 3

维护凸包时不要使用 vector，使用数组和指针静态分配内存。这样进一步减少了 vector 动态内存分配的压力。

4.4 优化 4

由于在块长不变的时候内存分配情况一定不会变，所以只需要在第一个块分配一下内存，最后一个块重新分配一下内存就可以了，不需要每次都重新分配。

4.5 优化 5

一杯茶，一包烟，一个块长调一天。

加上这些常数优化，我就轻松（？）过掉了这题。

上面的常数优化大部分都围绕着消除动态分配内存导致的巨大常数，这个思路在其他场景下也适用。

为了防止抄袭，这里仅贴出数据结构核心部分的代码，请读者自行完成其余部分（雾）