# 插火把：题解

## 解法比较

出题人解法用 $u=x+y$ 、$v=x-y$ 把曼哈顿菱形变为轴对齐正方形，并将合法格点按共同奇偶性拆成两组压缩坐标，在两组中做矩形差分与前缀和。只有同奇偶的 $u,v$ 才能还原整数格点，因此这种拆分既避免误计也保持覆盖条件。下文完整解释了同一算法。

压缩边界可按端点奇偶分类计算，也可统一使用向上、向下取整；Codex（GPT-6）的实现采用后者。设网格边长为 $n,m$ ，两者时间和空间上界均为 $O((n+m)^2)$ ，另需读入并输出网格。

## 将菱形变为矩形

使用坐标变换 $u=x+y$ 、$v=x-y$ .恒等式

$$|x-i|+|y-j|=\max\{|u-(i+j)|,|v-(i-j)|\}$$

将半径为 $R$ 的严格不等式转换成两维均为闭区间的矩形：

$$i+j-R+1\le u\le i+j+R-1$$
$$i-j-R+1\le v\le i-j+R-1$$

对矩形做二维差分更新，全部更新完成后用二维前缀和恢复亮度。

## 按奇偶压缩

原网格中的整数点满足 $u\equiv v\pmod2$ .若保存整个旋转坐标矩形，约一半位置不会对应整数网格点。分别建立偶数和奇数坐标网格，将每维间隔为二的坐标压缩为连续下标。

对每个光源，在两个网格中分别找到矩形内最小和最大的对应奇偶坐标。先与该网格全局坐标范围相交，再向内取整到正确的奇偶性；区间为空则跳过。每个非空矩形做四次差分修改。$R=0$ 时直接略去。

有些变换后的位置虽然是整数点，却仍在农田之外。保留这些辅助位置不会影响正确性，最终只查询实际农田格子的坐标。

## 正确性

坐标恒等式使原作用范围与变换后的矩形完全等价，并保留严格边界。奇偶拆分将每个实际格子放入且只放入一个压缩网格。二维差分与前缀和使每个格子恰好获得所有覆盖它的光源贡献。最后逐格检查亮度是否不超过自身阈值，因此计数正确。

## 复杂度与实现

令 $H=n+m$ .两个压缩网格合计 $O(H^2)$ 个位置；时间为 $O(nm+H^2)$ ，空间为 $O(H^2)$ .最大规模下，差分数组合计约 $74$ MiB，符合 $128$ MB 的内存限制。

输入光源时直接更新差分，恢复亮度后再流式读取阈值，无需保存整份输入。亮度和差分使用 64 位整数；参考程序使用缓冲读取处理大规模输入。