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

BBztk · 2026-05-09 15:51:48 · 题解

我写这篇题解主要作用是帮助那些需要卡常的，如果需要学习主要做法的话可以参考 Sol1 大佬的这篇文章。

在这道题上我的代码拿到了最优解，总时间 9.51s（未开 O2），单点最慢 626ms，唯一一个跑进 10s 内的。
由于一些神秘的原因，开了 O2 反而变慢了，跑了个 9.68s。

1. 带权分块：

针对 80pts 被卡最后5个 Hack 数据的，能优化很多时间。
首先带权分块和普通分块的主要区别就是块长，普通分块固定块长对于随机数据跑得很快，但是对于 Hack 的构造数据会被卡飞，原因就是它的时间复杂度核心并不是普通的 块数 \times m，而是 \sum 散块的修改次数 \times 块长，如果某些位置被大量散块修改覆盖，固定块长会让这些热点块代价很高。带权分块就是先根据操作分布估计每个候选块 [L,R] 的代价，然后用 DP 选块边界。
然后就是代价模型，一般用的是 散块修改次数 \times 块长+整块查询次数 \times KK，其中 KK 是一个等块查询的等效常数，散块修改贵，因为会触发块内线段树 pull，重建凸包；整块查询相对便宜，因为可以离线排序后双指针扫。
实现时不需要枚举所有 L,R，否则 DP 本身太慢。一般只允许右端点是 D 的倍数，并限制最大块长 AX。针对本道题用的参数：D=100, AX=5000, KK=15。

感谢 王熙文 在这篇中提供的参数，让我减少了很多调参的时间。

2. 块内凸包不要用 vector：

这个是较为一般的卡常方式了，但确实能节省很多时间，那我就来解释一下原因吧。
块内线段树的每个节点都要维护三类凸包：前缀最优值的凸包、后缀最优值的凸包、最大子段和的凸包。如果这些凸包使用动态容器保存，那么每次重建节点时可能发生清空、扩容、重新分配、析构、拷贝等操作。
显然这道题的数据中会出现大量这种操作，动态内存分配的成本会非常高，而且会破坏缓存局部性。
更快的方式是使用预先分配好的连续内存池。每个节点只记录自己在内存池中的起始位置和凸包长度。这样所有凸包点都放在连续数组里，避免堆分配，访问也更集中。

这种是针对运算较底层的优化了，一般只用使用就行了，不需要知道原理。

3.整块查询：

整块查询时，只需要查询块根节点上的凸包。如果每次查询都在凸包上二分，会多一个对数，而且常数不小。
更好的做法是逐块离线处理。处理某个块时，遇到整块查询先不立刻回答，而是记录当时这个块的整体加标记和询问编号。等到必须处理这些查询时，把它们按整体加标记排序。
排序后，凸包上的最优点会单调移动，可以用指针扫，而不是每次二分。也就是说，一批整块查询可以接近线性处理。

4. 排序优化：

用整数基数排序，原因不用多说。
但小批量事件用插入排序，如果某次积攒的整块查询事件很少，基数排序反而不划算。因为基数排序每次都要清空桶、扫描多轮，即使只有几十个元素，也要付固定成本。
小数组用插入排序更快。尤其这题里，事件的整体加标记经常局部接近有序，插入排序在这种情况下常数很低。

如果有序就跳过排序：

在积攒整块查询事件时，可以顺便判断当前整体加标记是否保持非降序。如果一直有序，那么处理时不需要排序，直接用指针扫凸包即可。
这个判断成本极低，只需要比较新加入的标记和上一个标记。对于某些数据，尤其是整体修改方向比较单一的数据，可以省掉大量排序时间。

这里也是针对构造数据的，随机数据基本没啥用。

5. 最大字段和优化：

一次区间查询最终要把很多块或很多线段树节点的结果合并起来。每个结果包含四个值：区间和、最大前缀和、最大后缀和、最大子段和。
如果每次合并都返回一个新的结构体，会产生大量临时对象。这个结构体一般有四个 64 位整数，大小不算小。频繁传值和返回会增加寄存器压力，也可能产生栈上的读写。
更快的方式是把右边结果直接合并进左边结果，也就是原地更新。这样可以减少临时对象和结构体拷贝。

简单来说就是如果你相信评测姬的实力就不用，实际 CCF 的评测姬跑得飞快，所以可以不用，但洛谷的评测姬的话……

6. 函数返回的优化：

块根查询和散块查询都会频繁返回四元信息。如果通过函数返回值返回，编译器虽然可能优化，但在递归和复杂控制流下不一定完全消掉。
解决方法是把结果对象传进去，让函数直接写入。这样减少返回大对象的开销，也降低寄存器分配压力。

用处不大，但很稳定，至少能保证对所有数据都有优化。

7. 快读快写：

优秀的快读快写可以极大的优化你的常数，感谢 Hootime 提供的代码，我也在这里放出来吧： :::info[Code]

#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){
    x = 0; int w = 1;
    char ch = gc();
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -w;
        ch = gc();
    }
    while(ch >= '0' && ch <= '9')
        x = (x<<3)+(x<<1)+(ch^48), ch = gc();
    x *= w;
}
template<typename T, typename... Args>
inline void read(T& x, Args&... y){
    return read(x), read(y...);
}

在本题中扔掉处理负数片段以获得更大优化。 :::

8. 操作数组扫描的优化：

一定要顺序扫描，不要盲目打包！！！

直觉上，把操作类型、左右端点、编号压到一个整数里，似乎能减少内存访问。但实际经常变慢。
每次处理操作时都需要解码，包括移位、掩码和类型判断。而且修改值仍然需要额外访问。相比之下，分开的数组虽然看起来多，但每一轮都是从头到尾顺序扫描，CPU 的预取效果很好。
另一种看似合理的优化是：提前把每个操作分发到它影响的块里，这样每个块不用扫所有操作。
但如果用链表或分散存储，会破坏顺序访问。CPU 很难预取链式跳转的数据，cache miss 会增加。而且一个长区间操作会被挂到很多块上，预处理数据量也会膨胀。
当前做法虽然每个块都顺序扫所有操作，但访问模式非常稳定，缓存友好。除非预分发做成非常紧凑的连续数组，否则容易变慢。

9. 凸包合并循环的优化：

散块修改最重的地方是重建线段树节点的信息。重建时要合并前缀凸包、后缀凸包、最大子段和凸包，还要做一次类似闵可夫斯基和的合并。
这些循环里会反复计算“某个点在当前整体加标记下的实际值”。如果每次都通过一个辅助函数计算，或者反复计算相邻两个点的实际值差，会浪费很多乘法和数组读取。
更好的方式是直接使用相邻点的差值：横坐标差乘标记，加上纵坐标差。这样能减少函数调用和重复乘法。

10. 关于 int128：

一般来说，人们会对超出 long long 范围的数值使用 __int128 存储，但你要知道，有些题目只是输入需要，并不是运算中也需要。
如果能证明数值不会溢出 64 位，就应该用 64 位整数。由于这题保证任意时刻单个元素绝对值不超过一定范围，块长又有限，很多地方的乘积实际不会超过 64 位范围。
但是这个优化有风险。如果证明不严谨，可能出现隐藏溢出导致错误答案。比较稳的做法是：只在最可能溢出的少数斜率比较处保留 128 位，其它地方用 64 位。
因为 64 位比 128 位快。

11.查询时要下传标记：

散块查询只读信息，不修改结构。查询递归时，可以把沿途经过的整体加标记累加成一个参数传下去。到达完整覆盖节点时，用这个累积标记去查询凸包。
这样查询不会改变线段树状态，也不会触发标记下传和重建。只有散块修改才需要下传标记，因为修改后要重新合并父节点信息。

12.合理安排批处理时机：

整块查询可以延迟批处理，但不能无限延迟。因为一旦出现散块修改，块内线段树结构会改变，之前积攒的查询必须在修改前处理掉。
这个貌似 O2 会帮你做（之前貌似看到过，但有些忘记了，如果写错了记得叫我），但自己做了肯定要好一点。
流程大概是这样： 遇到整块修改，只更新块的整体加标记。
遇到整块查询，记录当前整体加标记和询问编号。
遇到散块查询，直接在线段树上查询。
遇到散块修改，先处理之前积攒的整块查询，再执行散块修改。
如果过早处理整块查询，排序批次变多，常数变大。如果过晚处理，会因为线段树状态改变而答案错误。

13.一些关于负优化的：

1. 首先是关于三目运算符，不要以为它和位运算长得像就以为它要快一点。
   现代 CPU 对稳定分支预测很强。如果一个条件的分布比较稳定，普通条件语句往往已经很好。
   三目表达式如果写得复杂，可能导致重复计算。特别是在凸包合并里，如果一个三目表达式中重复计算多个点的实际值，反而会变慢。
2. 不要把点结构强行压缩对齐，凸包上的每个点包含一个长度和一个对应的最优值。长度是较小整数，值是 64 位整数。按正常结构体存储时，中间可能有填充字节，看起来浪费空间。
   但如果强行压缩结构体，64 位整数可能变成非对齐访问。非对齐访问虽然在某些 CPU 上可以运行，但通常更慢，而且可能跨缓存行。
   这题凸包点的 64 位值是热路径中高频读取的数据，所以应保持自然对齐，不要强行压缩！
3. 不要给所有大数组强行缓存行对齐。缓存行对齐对某些小而热的数据有用，比如排序桶。但如果给大量大数组都强行对齐，可能扩大内存布局，增加页表和缓存压力。
   大数组的访问模式更重要。顺序访问的大数组，即使没有手动对齐，也能被 CPU 预取很好地处理。乱加对齐不一定有收益，甚至可能变慢。

   4. O2 可能对你的代码负优化！！！非常重要！！！

14. 调参：

不说了好吧，一杯茶，一包烟，一个块长调一天。 嗯……还是写一下吧： :::info[调块长的技巧] 分块调参的方法不是取根号，而是先写出这份分块的真实代价模型，然后按模型求一个理论块长，再围绕这个值实测微调。不同分块的最优块长差别很大，\sqrt n 只是最常见的一种特例。
设块长为 B，块数大约是 n/B。
很多分块操作的代价可以拆成两类：
一种是散块代价，也就是区间左右两端不完整块的处理。它通常和 B 成正比。
另一种是整块代价，也就是中间完整块的处理。它通常和 n/B 成正比。
所以最常见模型是：单次操作代价 \approx C_1 \times B + C_2 \times n / B。
如果两边常数差不多，最优块长就是：B=\sqrt n;
但实际常数经常不一样，所以更准确是：B = \sqrt {\frac{C_2 \times n} {C_1}}。
也就是说，如果散块处理特别贵，就应该减小块长；如果整块处理特别贵，就应该增大块长。
有些分块里，散块只是暴力扫元素，而整块查询只读一个预处理值。这时散块常数大，整块常数小，块长应该偏小。
如果整块处理要做二分、排序、合并结构，整块常数大，块长应该偏大，减少块数。 经验上：

• 散块贵：块长取小一点；
• 整块贵：块长取大一点；
• 重构贵：块长取小一点；
• 每块初始化贵：块长取大一点；
• 每次都扫所有块：块长取大一点；
• 每次都暴力扫散块：块长取小一点；

带修改的分块经常会出现“散块修改后重构整个块”的情况。
如果一次散块修改要重构一个块，重构代价是 O(B \log B) 或 O(B)，那么散块修改会很贵。此时块长不能太大。
模型可能变成：

• \log^2 B
• B 的一小部分

如果散块已经不那么贵，那么可以适当增大块长来减少块数。
现在这类题就是典型例子：散块查询不算特别重，真正重的是散块修改造成的凸包重构。因此调块长时不能只看查询，要重点看修改分布。

普通莫队常见块长是 \sqrt n，但更准确的模型是：

• 左端点移动代价 \approx 查询数 \times B
• 右端点移动代价 \approx \frac{n^2}{B}

所以最优块长大约是：B \approx \frac{n}{\sqrt{查询数}}。
如果查询数和 n 同阶，就是 \sqrt n。
如果查询数远大于 n，块长应该更小；
如果查询数远小于 n，块长应该更大。

带修改莫队有三个维度：左端点、右端点、时间。块长一般和 n^{\frac{2}{3}} 有关。
粗略经验是：