#P4800. [CEOI2015 Day2] 核能国度

[CEOI2015 Day2] 核能国度

题目描述

核能国可以看作一个由 W×HW \times H 的方格组成的矩形。核能国有 NN 个核电站,每个核电站占用一个方格。不幸的是,核能国遭遇了百年一遇的特大地震,导致所有的核电站都发生了核泄漏。

每个核电站的核泄漏程度可以用两个整数 a,ba, b 来表示。如果位于 P=[xP,yP]P=[x_P,y_P] 的核电站爆炸,方格 C=[xC,yC]C=[x_C,y_C] 会增加 max(0,\mathrm{max}(0, ab×d(P,C))a-b\times d(P,C)) 贝克的辐射(贝克是单位),其中 d(P,C)d(P,C) 是两个方格的切比雪夫距离,即 d(P,C)=d(P,C) = max(xPxC,\mathrm{max}(|x_P - x_C|, yPyC)|y_P - y_C|)

一个方格可能会受到多处核泄漏的影响。

例如,如果一个 a=7,a = 7, b=3b = 3 的核电站爆炸了,所在的方格 XX 会受到 77 贝克辐射(贝克是单位),满足 d(X,Y)=1d(X,Y) = 188 个方格 YY 会受到 44 贝克辐射,满足 d(X,Z)=2d(X,Z) = 21616 个方格 ZZ 会受到 11 贝克辐射。

环保部门给了你 QQ 组询问,每组询问会划定核能国领土中的一个矩形,请回答:矩形区域内(每个方格)所受的平均辐射量为多少。

输入格式

第一行,两个正整数 WWH(W×H2.5×106)H(W × H \leq 2.5×10^6),分别表示核能国的宽度与高度。

第二行,一个正整数 NN,表示核电站的个数 (1N2×105)(1 \leq N \leq 2×10^5)

在接下来的 NN 行中,每行四个正整数 $x_i,y_i,a_i,b_i(1 \leq x_i \leq W,1 \leq y_i \leq H,1 \leq a_i,b_i \leq 10^9)$,表示有一个核电站位于方格 [xi,yi][x_i,y_i],它的参数为 aia_ibIb_I。每个格子最多有一个核电站。

N+3N+3 行,一个正整数 QQ,表示询问的次数 (1Q2×105)(1 \leq Q \leq 2×10^5)

在接下来的 QQ 行中,每行四个 正整数 $x_{1j},y_{1j},x_{2j},y_{2j}(1 \leq x_{1j} \leq x_{2j} \leq W,1 \leq y_{1j} \leq y_{2j} \leq H)$,表示该询问给出的矩形区域的左上角在 [x1j,y1j][x_{1j},y_{1j}] 且它的右下角在 [x2j,y2j][x_{2j},y_{2j}]

你可以假设核能国内的总辐射量少于 2632^{63}

输出格式

对于每个询问,输出一行表示给定矩形区域内所有方格的平均辐射量,四舍五入至整数。

4 3
2
1 1 7 3
3 2 4 2
4
1 2 2 3
1 1 4 3
4 2 4 2
1 3 4 3
4
4
2
2

提示

以下为两次爆炸后对每个方格产生的辐射量:

7 6 3 2
4 6 5 2
1 3 3 2
  • 222^2 方形区域内的总辐射为 1414,所以平均值为 14÷4=3.514\div 4=3.5,四舍五入至 44

  • 整个核能国的总辐射为 4444,所以平均值为 44÷123.6744\div 12 \approx 3.67,四舍五入至 44

  • 单个格子的平均辐射量就是它所受到的辐射量。

  • 最后一行的平均辐射量为 9÷4=2.259\div 4=2.25,四舍五入至 22

有 14 组测试数据。奇数的测试组只包含 aabb 的倍数的核电站。对每个子任务的进一步限制如下:

测试组 进一步限制 分数
11 H=1,NW108,QW108H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8 33
22 22
33 $N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$ 33
44 22
55 H=1,NW108H=1,N\cdot W \leq 10^8 66
66 44
77 NWH108N\cdot W \cdot H \leq 10^8 66
88 44
99 H=1H=1 1515
1010 1010
1111 没有符合界限定义的爆炸事件 1515
1212 1010
1313 1212
1414 88

如果核电站位于核能国的边境或是在离边境稍近的位置,那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作界限