# 真空内爆弹：题解

> 并列方案：仿射矩阵。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。


## 把操作写成仿射变换

每个操作都能写为 $v'=Av+t$ ，其中 $v=(x,y)^\mathsf{T}$ ，$A$ 为 $2\times2$ 矩阵，$t$ 为平移向量。平移的矩阵为单位矩阵，四种对称的矩阵依次为

$$\begin{pmatrix}1&0\\0&-1\end{pmatrix},\quad
\begin{pmatrix}-1&0\\0&1\end{pmatrix},\quad
\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad
\begin{pmatrix}0&-1\\-1&0\end{pmatrix}$$

逆时针旋转的矩阵是

$$\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$$

先做 $(A_1,t_1)$ ，再做 $(A_2,t_2)$ ，合成结果为

$$(A_2A_1,\ A_2t_1+t_2)$$

乘法顺序不能交换；后来的旋转或对称也会作用于此前累计的平移。

## 线段树

按点的编号建线段树，每个节点维护尚未下传的仿射变换。区间完全覆盖时，将新变换合成到旧标记之后。部分覆盖或向下查询时，把父标记合成到两个子节点之后，再把父标记重置为恒等变换。

叶节点以初始坐标作为平移向量，相当于把原点变换到该点。所有后续变换合成后，叶节点的平移向量就是当前坐标。单点查询沿途下传标记；最后遍历全部叶节点，按编号输出。

## 正确性

仿射合成公式与依次执行两个操作完全相同。维护不变式：每个节点的标记表示其子树尚未收到的、按时间顺序执行的变换。完全覆盖时追加新操作，部分覆盖前下传较早的操作，均保持这一不变式。查询到叶节点时，全部相关操作已按输入顺序合成，因此得到正确坐标；最终遍历同理。

## 精度与复杂度

参考程序使用 `long double` 保存六个仿射系数，输出八位小数。每次区间修改或单点查询为 $O(\log n)$ ，建树和最终输出为 $O(n)$ ，总时间 $O(n+m\log n)$ ，空间 $O(n)$ .

随题提供 `tests/checker.cpp` ，编译后按 `checker input reference contestant` 调用。它根据输入统计查询数量，检查全部坐标、缺失或额外输出，以及非有限数值；每个坐标按绝对误差 $0.05$ 检查，并附 $10^{-6}$ 的比较舍入余量。