P4800 [CEOI 2015] 核能国度 (Day2)

核能国可以看作一个由 $W \times H$ 的方格组成的矩形。核能国有 $N$ 个核电站，每个核电站占用一个方格。不幸的是，核能国遭遇了百年一遇的特大地震，导致所有的核电站都发生了核泄漏。 每个核电站的核泄漏程度可以用两个整数 $a, b$ 来表示。如果位于 $P=[x_P,y_P]$ 的核电站爆炸，方格 $C=[x_C,y_C]$ 会增加 $\mathrm{max}(0,$ $a-b\times d(P,C))$ 贝克的辐射（贝克是单位），其中 $d(P,C)$ 是两个方格的切比雪夫距离，即 $d(P,C) =$ $\mathrm{max}(|x_P - x_C|,$ $|y_P - y_C|)$。 一个方格可能会受到多处核泄漏的影响。 例如，如果一个 $a = 7,$ $b = 3$ 的核电站爆炸了，所在的方格 $X$ 会受到 $7$ 贝克辐射（贝克是单位），满足 $d(X,Y) = 1$ 的 $8$ 个方格 $Y$ 会受到 $4$ 贝克辐射，满足 $d(X,Z) = 2$ 的 $16$ 个方格 $Z$ 会受到 $1$ 贝克辐射。 环保部门给了你 $Q$ 组询问，每组询问会划定核能国领土中的一个矩形，请回答：矩形区域内（每个方格）所受的平均辐射量为多少。

无

无

以下为两次爆炸后对每个方格产生的辐射量： ```plain 7 6 3 2 4 6 5 2 1 3 3 2 ``` - $2^2$ 方形区域内的总辐射为 $14$，所以平均值为 $14\div 4=3.5$，四舍五入至 $4$。 - 整个核能国的总辐射为 $44$，所以平均值为 $44\div 12 \approx 3.67$，四舍五入至 $4$。 - 单个格子的平均辐射量就是它所受到的辐射量。 - 最后一行的平均辐射量为 $9\div 4=2.25$，四舍五入至 $2$。 有 14 组测试数据。奇数的测试组只包含 $a$ 是 $b$ 的倍数的核电站。对每个子任务的进一步限制如下： |测试组|进一步限制|分数| |:-:|:-:|:-:| |$1$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$3$| |$2$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$2$| |$3$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$3$| |$4$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$2$| |$5$|$H=1,N\cdot W \leq 10^8$|$6$| |$6$|$H=1,N\cdot W \leq 10^8$|$4$| |$7$|$N\cdot W \cdot H \leq 10^8$|$6$| |$8$|$N\cdot W \cdot H \leq 10^8$|$4$| |$9$|$H=1$|$15$| |$10$|$H=1$|$10$| |$11$|没有符合**界限**定义的爆炸事件|$15$| |$12$|没有符合**界限**定义的爆炸事件|$10$| |$13$|无|$12$| |$14$|无|$8$| 如果核电站位于核能国的边境或是在离边境稍近的位置，那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作**界限**。