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

王熙文 · 2025-04-22 17:59:52 · 题解

提供一个最大点 656ms，总时间 7.79s 的做法，目前最优解第一。

思路

和主流的做法相同。

如果没有修改，这是一个经典的线段树问题：对线段树上每个区间维护 \text{sum},\text{lmax},\text{rmax},\text{ans} 表示区间总和、前缀和的最大值、后缀和的最大值、最大子段和。每次合并的时候，最大子段和为两边最大子段和、左子树 \text{rmax} 加右子树 \text{lmax} 的最大值。

如果是全局加，上面维护的问题出于不同区间长度的增量是不同的。注意到增量是一个一次函数，所以可以对每个节点维护一个长度作为横坐标、该长度的区间最大值作为纵坐标的凸包。每次合并时 \text{sum} 并不好维护，但是注意到一并记录 \text{lmax},\text{rmax} 的凸包后 \text{sum} 就是左子树 \text{rmax} 与右子树 \text{lmax} 的闵可夫斯基和。对差分数组归并排序即可。

对于查询，需要在每个线段树上的节点二分。可以将所有值离线并排序，之后就只需要双指针了。这样就解决了 P5073（这道题里还需要将询问和维护的东西放在一起递归以卡空间）。

对于原题，考虑分块。对于整块的修改就相当于全局加，因此对每个块维护上面的线段树。接下来整块的修改就只需要打标记了。但是问题出在，散块需要重构这个线段树，而它的构建是 \mathcal O(B \log B) 的。发现散块未必需要重构，操作在散块上仍然是一个区间加。注意到一次修改，线段树每层上只有两个点需要 push_down 和 push_up（当一个区间开始被分裂后两边只有一个儿子会再次递归），所以暴力修改的复杂度是 \mathcal O(B) 的。

考虑查询。注意到对每个块只需要求出 \text{sum},\text{lmax},\text{rmax},\text{ans} 这四个数，然后合并即可，因此每一个块是独立的。整块的查询需要在根节点二分，时间会多一个 \log。两个散块修改之间每个查询本质上是整块修改标记累加的数，使用基数排序将这些数排序再双指针即可去掉一个 \log。使用分散层叠算法也是可以的，但是需要在线，空间可能会出问题。散块的查询只需要在线段树上做普通的查询即可。

因为每个块是独立的，所以可以逐块处理，以减少空间复杂度。

一些常规的卡常技巧

• 散块查询时无须 push_down，而是直接记录一个变量传下来 \text{tag}。这样它的复杂度就不是 \mathcal O(B)，而是 \mathcal O(\log^2 B) 的了。
• 计算斜率的时候转成 __int128 相乘比 double 快。
• 做闵可夫斯基和时需要维护一个数组记录每个长度的答案是多少。在对这个数组求凸包时，没有被遍历过的位置不合并。
• push_down 的时候如果没有标记直接返回。
• 基数排序时桶的大小设为 256。一方面是因为可以卡进 cache，另一方面是因为需要做 \mathcal O(n) 次基数排序（相当于散块修改的个数），如果太大了乘上 n 已经过不去了。
• 对排序的长度分治，如果很大才用基数排序。或者索性将基数排序删了，实测（与分治相比）没有任何速度变化。
• 散块修改时如果修改的左端点与块的左端点重合，可以认为是整块，右端点同理。
• 将所有 vector 换成指针，放到一个大的内存池里。这是为了防止 vector 动态开空间产生的消耗。
• 排序的时候将 pair（一个值是标记之和，另一个值是查询的时间）压成一个数。因为题目保证了任意时刻的绝对值，所以标记之和 \in [-4 \times 10^9,4 \times 10^9]，再乘上 n 的大小不会爆。
• 讨论区里看到的神秘块长 B=408，实测对于最后一个点可以快 100ms。

一个非常规的卡常技巧

这个技巧我之前没见过，是我自己想出来的，所以想推广一下。

考虑使用 dp 求出最佳的块的分配。发现复杂度瓶颈在散块的修改和整块的查询。对于一个块 [L,R]，将复杂度抽象成下面的模型：

• 对于修改 [l,r]，代价为 l \in (L,R],r \in [L,R) 成立的个数乘上 R-L+1。
• 对于查询 [l,r]，若 [L,R] \in [l,r]，代价为 k（k 为一个常数）。

普通的 dp 会超时，但是注意到贡献满足四边形不等式（可以通过简单分讨证明），因此可以使用单调栈加二分解决。计算一个块的代价时，第一类贡献可以使用前缀和解决，第二类贡献可以使用主席树解决。

但是这个 dp 是 \mathcal O(n \log^2 n) 的，自身会产生一些消耗。注意到只需要一个近似的解，因此考虑强制要求块的 r 是 \text{div} 的倍数，这样复杂度就可以除以 \text{div}。

这样 dp 出来的块有可能会很长导致空间超限，因此再设一个 \text{axlen} 表示最长的块，如果超过了 \text{axlen}，在计算贡献时直接返回极大值。这样仍然是满足四边形不等式的。

我的代码中三个参数分别为：k=15,\text{div}=100,\text{axlen}=5000。

这个技巧对于非随机数据的优化效果非常大。

提交记录