真空内爆弹题解

解法与取舍

出题人解法：交换、符号、旋转与平移专用标记。 两种表示均为 $O(n+m\log n)$ 时间、$O(n)$ 空间。专用标记作为标程，测量中的峰值内存较低；仿射矩阵在混合操作输入上略快，且使用统一的复合公式。两者并列介绍，实际差异取决于操作分布和浮点实现。

程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的仿射矩阵见 alternative.cpp 和并列方案题解。

一个标记依次表示：交换两坐标、分别改变符号、旋转、平移。用 $P$ 表示交换，$D$ 表示对角符号矩阵，$R(\theta)$ 表示旋转，$t$ 表示平移，则

$$v\longmapsto R(\theta)DPv+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}$ 的比较余量，并拒绝缺失、多余或非有限数值。

各方案的五次重复计时与峰值内存记录见评测环境与性能。