自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 21:56:41，当前版本为作者最后更新于2020-07-13 22:47:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

---

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

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

---

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