来个hack

Ruiqun2009 @ 2022-05-07 16:06:45

by zhang_kevin @ 2022-05-27 18:25:04

怎么做到的？？？

我也A了P5073，为什么这道题死活过不去？？？

by big_teacher_brother @ 2022-05-28 14:25:05

@Ruiqun2009 orz

by Ruiqun2009 @ 2022-05-28 16:27:14

把整个序列按照加的字段分段，也就是说，每一段要么全加，要么不加。然后就是每一段里的最大子段和，再用P5073的代码就可以过了。

by Ruiqun2009 @ 2022-05-28 16:34:23

与P5073相比，唯一不变的还是两个字：分块

但有的东西你想不到就真的想不到了。。。

分块做区间加区间和做过吗？

是不是每个操作都是从左往右，小段----大段----小段，这样？

你试过按块处理问题吗？

就是对第一块扫描n个问题，然后再去下一个块

这里就有一个重要的思想，前提是数据可以合并，势必能均摊

我们知道小段共有n个，单次操作复杂度O(\sqrt n)

又有大段 n\sqrt n个，单次操作复杂度O(1) 均摊下来每个块的复杂度是O(n)的，刚好有\sqrt n 个块

所以——你懂得，这玩意用在这里真的真的真的，女少口阿

如图，黑色为块的分界，绿色为询问，红色为修改，下面一段字的n和m表示规模

我们知道，有m条红色，就可以通过分块变成m条小块的红色，和m\sqrt n 条整段的红色

又有m条绿色，就可以通过分块变成m条小块的绿色，和m\sqrt n 条整段的绿色

其中绿色中的小块我们可以暴力解决

那么对于任意一个块中，就会出现如下情况

不妨设为最坏情况，有最多m条绿色大段和最多m条红色大段 交错 在一个块里

那红色小段？。。。

大段的总量是红色小段总量的\sqrt n 倍，即红色小段是极为稀疏的

然后只要把这玩意一圈

天哪这不就是P5073！

不说了。。。你们加油

by Ruiqun2009 @ 2022-05-28 16:35:17

建议块长420

by zhang_kevin @ 2022-05-28 16:35:24

@Ruiqun2009 谢谢

by Ruiqun2009 @ 2022-05-28 16:37:26

其实就是@2018heyuyang的题解，我只是转载了一下而已

by MysteriousProgrammer @ 2022-05-29 15:01:31

@Ruiqun2009 所以您到底在P5073的代码上改了些啥(虽然这道题我没AC)？@2018heyuyang 的题解看不懂······

by Ruiqun2009 @ 2022-05-29 15:17:32

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

1. 零散修改优化

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

不要忘了：

1. 线段树的子树还是线段树

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

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

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

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

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

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

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

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)。

剪枝们，上！

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

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

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

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

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

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

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

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

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

by Ruiqun2009 @ 2022-05-29 15:18:19

的确，又是一篇题解。

但是它更容易理解。