真空内爆弹 题解¶
解法与取舍¶
出题人解法：交换、符号、旋转与平移专用标记。 两种表示均为 \(O(n+m\log n)\) 时间、\(O(n)\) 空间。专用标记作为标程，测量中的峰值内存较低；仿射矩阵在混合操作输入上略快，且使用统一的复合公式。两者并列介绍，实际差异取决于操作分布和浮点实现。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的仿射矩阵见 alternative.cpp 和并列方案题解。
标记的规范顺序¶
一个标记依次表示：交换两坐标、分别改变符号、旋转、平移。用 \(P\) 表示交换，\(D\) 表示对角符号矩阵，\(R(\theta)\) 表示旋转，\(t\) 表示平移，则
标记保存交换标志、两个取反标志、旋转的正弦与余弦以及两个平移分量。叶节点初始仅保存对应坐标作为平移；节点无需维护区间坐标和，本题只查询单点并在最后输出全部点。
如何把新变换接在旧标记之后¶
逐项应用新标记的操作，保持规范顺序：
- 新交换：交换旧平移分量和旧取反标志，翻转交换标志，将旧旋转的正弦取反。
- 新的单轴取反：取反对应平移分量、翻转对应符号标志，并将旧正弦取反。
- 新旋转：旋转旧平移向量，再用角度和公式合并正弦、余弦。
- 新平移：直接加到已变换的旧平移量上。
前两项使用反射与旋转的恒等式 \(FR(\theta)=R(-\theta)F\) .交换还满足 \(PD=D'P\) ，其中 \(D'\) 的两个对角项交换。因此这些更新与先执行旧标记、再执行新标记完全相同。特别要注意，后来的旋转或反射必须同时作用于此前的平移量。
线段树及正确性¶
按编号建树。整段覆盖时将新操作接到当前延迟标记之后；部分覆盖或单点查询时，将父标记接到两个子标记之后，再清空父标记。
保持不变量：每个标记恰好表示其子树尚未收到的、按时间排列的操作。正确的复合公式保持这一不变量；访问叶节点时，全部相关操作均已依次作用于其初始坐标，叶标记的平移量就是答案。最终遍历一次所有叶子即可输出最终状态。
复杂度与数值¶
建树与最终输出为 \(O(n)\) ；每次区间修改或单点查询为 \(O(\log n)\) ，总时间 \(O(n+m\log n)\) ，空间 \(O(n)\) .树的递归深度只有 \(O(\log n)\) .
标记使用 long double ，输出八位小数。专用表示和矩阵表示都存在浮点舍入。随题的 checker.cpp 按每坐标绝对误差 \(0.05\) 比较，另给 \(10^{-6}\) 的比较余量，并拒绝缺失、多余或非有限数值。
验证与性能¶
各方案的五次重复计时与峰值内存记录见评测环境与性能。