插火把：题解¶
解法比较¶
出题人解法用 \(u=x+y\) 、\(v=x-y\) 把曼哈顿菱形变为轴对齐正方形，并将合法格点按共同奇偶性拆成两组压缩坐标，在两组中做矩形差分与前缀和。只有同奇偶的 \(u,v\) 才能还原整数格点，因此这种拆分既避免误计也保持覆盖条件。下文完整解释了同一算法。
压缩边界可按端点奇偶分类计算，也可统一使用向上、向下取整；Codex（GPT-6）的实现采用后者。设网格边长为 \(n,m\) ，两者时间和空间上界均为 \(O((n+m)^2)\) ，另需读入并输出网格。
将菱形变为矩形¶
使用坐标变换 \(u=x+y\) 、\(v=x-y\) .恒等式
将半径为 \(R\) 的严格不等式转换成两维均为闭区间的矩形：
对矩形做二维差分更新，全部更新完成后用二维前缀和恢复亮度。
按奇偶压缩¶
原网格中的整数点满足 \(u\equiv v\pmod2\) .若保存整个旋转坐标矩形，约一半位置不会对应整数网格点。分别建立偶数和奇数坐标网格，将每维间隔为二的坐标压缩为连续下标。
对每个光源，在两个网格中分别找到矩形内最小和最大的对应奇偶坐标。先与该网格全局坐标范围相交，再向内取整到正确的奇偶性；区间为空则跳过。每个非空矩形做四次差分修改。\(R=0\) 时直接略去。
有些变换后的位置虽然是整数点，却仍在农田之外。保留这些辅助位置不会影响正确性，最终只查询实际农田格子的坐标。
正确性¶
坐标恒等式使原作用范围与变换后的矩形完全等价，并保留严格边界。奇偶拆分将每个实际格子放入且只放入一个压缩网格。二维差分与前缀和使每个格子恰好获得所有覆盖它的光源贡献。最后逐格检查亮度是否不超过自身阈值，因此计数正确。
复杂度与实现¶
令 \(H=n+m\) .两个压缩网格合计 \(O(H^2)\) 个位置；时间为 \(O(nm+H^2)\) ，空间为 \(O(H^2)\) .最大规模下，差分数组合计约 \(74\) MiB，符合 \(128\) MB 的内存限制。
输入光源时直接更新差分，恢复亮度后再流式读取阈值，无需保存整份输入。亮度和差分使用 64 位整数；参考程序使用缓冲读取处理大规模输入。