题目大意

有一个 $W \times H$ 的网格，$N$ 个核电站发生泄漏。每个核电站 $(x_i,y_i)$ 有参数 $a_i,b_i$，对格子 $(x,y)$ 的辐射贡献为 $\max(0, a_i - b_i \cdot \max(|x-x_i|,|y-y_i|))$。回答 $Q$ 个矩形查询，求矩形内所有格子的平均辐射值（四舍五入到整数）。

算法思路

核心思想

二维差分 + 分类处理，将辐射分布分解为不同方向的贡献。

关键观察

辐射值随切比雪夫距离线性递减，形成菱形影响区域

可以将影响区域分解为：

中心矩形区域：恒定斜率 $b$

四个三角形边界区域：需要特殊处理

角部区域：单独计算

算法步骤

1. 预处理差分数组

使用多个差分数组：

Sa[][]：存储主要辐射值

Sb[][]：沿主对角线方向的差分

Sc[][]：沿副对角线方向的差分

p[], q[]：处理边界情况的差分

2. 处理每个核电站

对于每个核电站 $(x,y,a,b)$：

计算影响半径 $c = \lfloor a/b \rfloor$

处理剩余部分 $d = a \bmod b$ 的矩形区域

处理主对角线方向的线性变化区域

处理副对角线方向的线性变化区域

处理边界超出网格的情况

3. 前缀和恢复

通过多次前缀和计算：

先恢复对角线方向的贡献

再恢复行和列方向的贡献

最后得到二维前缀和数组

4. 回答查询

利用二维前缀和 $O(1)$ 计算矩形和，求平均值并四舍五入。

算法流程

初始化：读入网格大小和核电站数据

差分标记：对每个核电站进行多方向差分标记

前缀和恢复：

恢复对角线贡献

恢复行列贡献

构建二维前缀和

处理查询：计算矩形区域平均值

输出结果：四舍五入到整数

复杂度分析

预处理：$O(N + WH)$，每个核电站 $O(1)$ 差分操作

查询：$O(Q)$，$O(1)$ 每次查询

空间：$O(WH)$，存储差分数组和前缀和

总结

本题是二维差分的高阶应用：

几何分解：将菱形影响区域分解为矩形和三角形

多方向差分：同时处理主对角线和副对角线方向

边界处理：妥善处理网格边界外的虚拟贡献

高效查询：通过预处理支持大量实时查询

这种"几何分解 + 多维度差分"的方法适用于许多具有特定衰减模式的辐射、影响传播问题，体现了计算几何与前缀和技巧的深度结合。