# 真空内爆弹 题解

## 解法与取舍

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

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

## 标记的规范顺序

一个标记依次表示：交换两坐标、分别改变符号、旋转、平移。用 $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](tests/checker.cpp) 按每坐标绝对误差 $0.05$ 比较，另给 $10^{-6}$ 的比较余量，并拒绝缺失、多余或非有限数值。

## 验证与性能

各方案的五次重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。