题目
题目描述
原题
核能国可以看作一个由$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$组询问，每组询问会划定核能国领土中的一个矩形，请回答：矩形区域内（每个方格）所受的平均辐射量为多少。
输入格式
第一行，两个正整数$W$和$H(W × H \leqslant 2.5×10^6)$，分别表示核能国的宽度与高度。
第二行，一个正整数$N$，表示核电站的个数$(1 \leq N \leqslant 2×10^5)$。
在接下来的$N$行中，每行四个正整数$x_i,y_i,a_i,b_i(1 \leqslant x_i \leqslant W,1 \leqslant y_i \leqslant H,1 \leqslant a_i,b_i \leqslant 10^9)$，表示有一个核电站位于方格$[x_i,y_i]$，它的参数为$a_i$与$b_i$。每个格子最多有一个核电站。
第$N+3$行，一个正整数$Q$，表示询问的次数$(1 \leq Q \leq 2×10^5)$。
在接下来的$Q$行中，每行四个 正整数 $x_{1j},y_{1j},x_{2j},y_{2j}(1 \leqslant x_{1j} \leqslant x_{2j} \leqslant W,1 \leqslant y_{1j} \leqslant y_{2j} \leqslant H)$，表示该询问给出的矩形区域的左上角在$[x_{1j},y_{1j}]$且它的右下角在$[x_{2j},y_{2j}]$。
你可以假设核能国内的总辐射量少于$2^{63}$。
输出格式
对于每个询问，输出一行表示给定矩形区域内所有方格的平均辐射量，四舍五入至整数。
样例
样例输入
1 | 4 3 |
样例输出
1 | 4 |
样例解释
以下为两次爆炸后对每个方格产生的辐射量：1
2
37 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 \leqslant 10^8,Q \cdot W \leqslant 10^8$ | 3 |
| 2 | $H=1,N\cdot W \leqslant 10^8,Q \cdot W \leqslant 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 |
如果核电站位于核能国的边境或是在离边境稍近的位置，那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作界限。
题解
暴力算法1
最暴力的算法你能想到什么？枚举！
对于每个核电站爆炸事件，枚举它周围的方格受到的影响
直接枚举整个国度显得太暴力了，我们能不能稍稍优化一下呢？
显然是可以的
我们发现，每个核电站爆炸事件有一个“势力范围”
只有在这个方格和核电站的切比雪夫距离$\leqslant\frac{a}{b}$时，它才会受影响
所以，我们只需要枚举这个核电站的势力范围就可以了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129//官方程序
typedef long long int huge;
int w, h, n, q;
typedef struct NUCLEARIA
{
huge Info[MAXWH];
huge& operator () (int x, int y) {return Info[(y * w) + x];}//其实就是个二维数组
}
NUCLEARIA;
typedef struct PLANT
{
int x;
int y;
int a;
int b;
}
PLANT;
typedef struct QUERY
{
int x1;
int y1;
int x2;
int y2;
}
QUERY;
NUCLEARIA Nuclearia;
PLANT Plant[MAXN];
QUERY Query[MAXQ];
int min(int a, int b)
{
return (a < b) ? a : b;
}
int max(int a, int b)
{
return (a > b) ? a : b;
}
int abs(int a)
{
return (a < 0) ? -a : a;
}
int dist(int x1, int y1, int x2, int y2)
{
return max(abs(x1 - x2), abs(y1 - y2));
}
void Print(huge sum, int area)//四舍五入
{
huge rsl = sum / area;
if((sum % area) * 2 >= area)
{
rsl++;
}
printf("%lld\n", rsl);
}
int main()
{
scanf("%d%d", &w, &h);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &(Plant[i].x), &(Plant[i].y), &(Plant[i].a), &(Plant[i].b));
Plant[i].x--;
Plant[i].y--;
}
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
scanf("%d%d%d%d", &(Query[i].x1), &(Query[i].y1), &(Query[i].x2), &(Query[i].y2));
Query[i].x1--;
Query[i].y1--;
}
for(int i = 0; i < n; i++)
{
PLANT& P = Plant[i];
int d = (P.a - 1) / P.b;
int x1 = max(0, P.x - d);
int y1 = max(0, P.y - d);
int x2 = min(w, P.x + d + 1);
int y2 = min(h, P.y + d + 1);
//势力范围
for(int x = x1; x < x2; x++)
{
for(int y = y1; y < y2; y++)
{
int d = dist(x, y, P.x, P.y);
Nuclearia(x, y) += P.a - (d * P.b);
}
}
}
for(int i = 0; i < q; i++)
{
QUERY& Q = Query[i];
huge rsl = 0;
for(int x = Q.x1; x < Q.x2; x++)
{
for(int y = Q.y1; y < Q.y2; y++)
{
rsl += Nuclearia(x, y);
}
}
Print(rsl, (Q.x2 - Q.x1) * (Q.y2 - Q.y1));
}
return 0;
}
暴力算法2
我们发现上面的算法在询问次数很多时是很耗时间的，因为每次我们都需要把矩形的辐射量加一遍
所以，我们可以在询问前先预处理一下
大家应该知道激光炸弹吧？我们可以借用一下这种矩阵的预处理方法，就是计算出左上角在$[1,1]$且它的右下角在$[x,y]$的矩形的总辐射，假设是$Nuclearia(x,y)$
最终的答案就是$Nuclearia(x_{2j},y_{2j})-Nuclearia(x_{1j}-1,y_{2j})-Nuclearia(x_{2j},y_{1j}-1)+Nuclearia(x_{1j}-1,y_{1j}-1)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141//官方程序
typedef long long int huge;
int w, h, n, q;
typedef struct NUCLEARIA
{
huge Info[MAXWH];
huge& operator () (int x, int y) {return Info[(y * w) + x];}//其实就是个二维数组
}
NUCLEARIA;
typedef struct PLANT
{
int x;
int y;
int a;
int b;
}
PLANT;
typedef struct QUERY
{
int x1;
int y1;
int x2;
int y2;
}
QUERY;
NUCLEARIA Nuclearia;
PLANT Plant[MAXN];
QUERY Query[MAXQ];
int min(int a, int b)
{
return (a < b) ? a : b;
}
int max(int a, int b)
{
return (a > b) ? a : b;
}
int abs(int a)
{
return (a < 0) ? -a : a;
}
int dist(int x1, int y1, int x2, int y2)
{
return max(abs(x1 - x2), abs(y1 - y2));
}
void Summarize()//预处理
{
for(int x = 0; x < w; x++)
{
for(int y = 0; y < h; y++)
{
if(x) Nuclearia(x, y) += Nuclearia(x - 1, y);
if(y) Nuclearia(x, y) += Nuclearia(x, y - 1);
if((x) && (y)) Nuclearia(x, y) -= Nuclearia(x - 1, y - 1);
}
}
}
void Print(huge sum, int area)//四舍五入
{
huge rsl = sum / area;
if((sum % area) * 2 >= area)
{
rsl++;
}
printf("%lld\n", rsl);
}
int main()
{
scanf("%d%d", &w, &h);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &(Plant[i].x), &(Plant[i].y), &(Plant[i].a), &(Plant[i].b));
Plant[i].x--;
Plant[i].y--;
}
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
scanf("%d%d%d%d", &(Query[i].x1), &(Query[i].y1), &(Query[i].x2), &(Query[i].y2));
Query[i].x1 -= 2;
Query[i].y1 -= 2;
Query[i].x2--;
Query[i].y2--;
}
for(int i = 0; i < n; i++)
{
PLANT& P = Plant[i];
int d = (P.a - 1) / P.b;
int x1 = max(0, P.x - d);
int y1 = max(0, P.y - d);
int x2 = min(w, P.x + d + 1);
int y2 = min(h, P.y + d + 1);
//势力范围
for(int x = x1; x < x2; x++)
{
for(int y = y1; y < y2; y++)
{
int d = dist(x, y, P.x, P.y);
Nuclearia(x, y) += P.a - (d * P.b);
}
}
}
Summarize();
for(int i = 0; i < q; i++)
{
QUERY& Q = Query[i];
huge rsl = Nuclearia(Q.x2, Q.y2);
if(Q.x1 >= 0) rsl -= Nuclearia(Q.x1, Q.y2);
if(Q.y1 >= 0) rsl -= Nuclearia(Q.x2, Q.y1);
if((Q.x1 >= 0) && (Q.y1 >= 0)) rsl += Nuclearia(Q.x1, Q.y1);
Print(rsl, (Q.x2 - Q.x1) * (Q.y2 - Q.y1));
}
return 0;
}
正解
接着，我们尝试在进一步的优化
回想一下我们在利用树状数组做区间修改时的方法：把区间的前面标记为$+a$，最后面标记为$-a$，这样，就可以进行区间修改了
我们可以借用一下这个思路，来标记一次核电站爆炸事件
首先，我们先找出这个核电站爆炸事件的“势力范围”，接着，把“势力范围”的左上角和右下角标记为$+a\% b$，把左下角和右上角标记为$-a\% b$
然后，我们开两个数组，在这个“势力范围”的对角线上（两条对角线，所以要两个数组）存储$b$的值，为了节省时间，我们可以只在4个角上标记，最后再把对角线上的数全部加出来
因为每个核电站爆炸事件的影响相等方格的，都会围成一个正方形（因为取的是切比雪夫距离），也就是说，我们在统计时，只需要先把对角线上的数复制到$Nuclearia$数组中，再把左边的和上面的数相加再减去左上的数就可以了
看起来有点抽象，我们可以再总结一下：
- 对于每个核电站爆炸事件，计算出它的“势力范围”，左上角为$(x1,y1)$，右下角为$(x2,y2)$
- 标记：$Nuclearia(x1,y1) = Nuclearia(x2,y2) = a\% b$，$Nuclearia(x1,y2) = Nuclearia(x2,y1) = a\% b$
- 修改两条对角线上的值（两条对角线的数组分别为$PosDiag$（主对角线）和$NegDiag$（次对角线））：$PosDiag(x1+1,y1+1)=b,PosDiag(x2,y2)=-b,NegDiag(x1+1,y2-1)=-b,NegDiag(x2,y1)=b$
- 枚举整个国度的$PosDiag$和$NegDiag$，$PosDiag(x,y)+=PosDiag(x-1,y-1),NegDiag(x,y)+=NegDiag(x-1,y+1)$
- 枚举整个国度的$Nuclearia$，$Nuclearia(x,y)+=PosDiag(x,y)+NegDiag(x,y)$
- 重复两次：枚举整个国度的$Nuclearia$，$Nuclearia(x,y)+=Nuclearia(x-1,y)+Nuclearia(x,y-1)-Nuclearia(x-1,y-1)$
这就是整个过程了，最后的答案计算方法和上面一样
你以为这就完了吗？
不！没完！
注意题目的最后一句话：如果核电站位于核能国的边境或是在离边境稍近的位置，那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作界限
也就是说$x1$和$y1$有可能$\leqslant 0$，$x2$也有可能$>W$，$y2$也有可能$>H$！
对于这个的处理，我们需要再开两个数组$Col$和$Row$，存储超出边界的部分，具体的实现就看程序吧，这些细节的处理，这里就不再细讲了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266//官方程序
typedef long long int huge;
int w, h, n, q;
typedef struct NUCLEARIA
{
huge Info[MAXWH];
huge& operator () (int x, int y) {return Info[(y * w) + x];}
}
NUCLEARIA;
typedef struct PLANT
{
int x;
int y;
int a;
int b;
}
PLANT;
typedef struct QUERY
{
int x1;
int y1;
int x2;
int y2;
}
QUERY;
NUCLEARIA Nuclearia, PosDiag, NegDiag;
PLANT Plant[MAXN];
QUERY Query[MAXQ];
huge Row[MAXWH];
huge Col[MAXWH];
int max(int a, int b)
{
return (a > b) ? a : b;
}
void UpdatePosDiag(int x1, int y1, int x2, int y2, int b)
{
if((x1 < 0) && (y1 < 0))
{
int m = -max(x1, y1);
Nuclearia(0, 0) += m * b;
x1 += m;
y1 += m;
}
if(x1 < 0)
{
int m = -x1;
Col[y1] += b;
Col[y1 + m] -= b;
x1 += m;
y1 += m;
}
if(y1 < 0)
{
int m = -y1;
Row[x1] += b;
Row[x1 + m] -= b;
x1 += m;
y1 += m;
}
PosDiag(x1, y1) += b;
if((x2 + 1 < w) && (y2 + 1 < h)) PosDiag(x2 + 1, y2 + 1) -= b;
}
void UpdateNegDiag(int x1, int y1, int x2, int y2, int b)
{
if(y2 > h - 1)
{
int m = y2 - (h - 1);
x1 += m;
y2 -= m;
}
if(x1 < 0)
{
int m = -x1;
Col[(y2 - m) + 1] -= b;
if(y2 + 1 < h) Col[y2 + 1] += b;
x1 += m;
y2 -= m;
}
if((x1 < w) && (y2 >= 0)) NegDiag(x1, y2) -= b;
if(x2 > w - 1)
{
int m = x2 - (w - 1);
x2 -= m;
y1 += m;
}
if(y1 < 0)
{
int m = -y1;
Row[(x2 - m) + 1] -= b;
if(x2 + 1 < w) Row[x2 + 1] += b;
x2 -= m;
y1 += m;
}
if((x2 + 1 >= 0) && (x2 + 1 < w) && (y1 - 1 >= 0) && (y1 - 1 < h)) NegDiag(x2 + 1, y1 - 1) += b;
}
void SummarizeDiags()
{
for(int x = 0; x < w; x++)
{
for(int y = 0; y < h; y++)
{
if((x) && (y)) PosDiag(x, y) += PosDiag(x - 1, y - 1);
if((x) && (y != h - 1)) NegDiag(x, y) += NegDiag(x - 1, y + 1);
}
}
}
void AddDiags()
{
for(int x = 0; x < w; x++)
{
for(int y = 0; y < h; y++)
{
Nuclearia(x, y) += PosDiag(x, y);
Nuclearia(x, y) += NegDiag(x, y);
}
}
}
void SummarizeLines()
{
for(int x = 1; x < w; x++)
{
Row[x] += Row[x - 1];
}
for(int y = 1; y < h; y++)
{
Col[y] += Col[y - 1];
}
}
void AddLines()
{
for(int x = 0; x < w; x++)
{
Nuclearia(x, 0) += Row[x];
}
for(int y = 0; y < h; y++)
{
Nuclearia(0, y) += Col[y];
}
}
void Summarize()
{
for(int x = 0; x < w; x++)
{
for(int y = 0; y < h; y++)
{
if(x) Nuclearia(x, y) += Nuclearia(x - 1, y);
if(y) Nuclearia(x, y) += Nuclearia(x, y - 1);
if((x) && (y)) Nuclearia(x, y) -= Nuclearia(x - 1, y - 1);
}
}
}
void Print(huge sum, int area)
{
huge rsl = sum / area;
if((sum % area) * 2 >= area)
{
rsl++;
}
printf("%lld\n", rsl);
}
int main()
{
scanf("%d%d", &w, &h);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &(Plant[i].x), &(Plant[i].y), &(Plant[i].a), &(Plant[i].b));
Plant[i].x--;
Plant[i].y--;
}
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
scanf("%d%d%d%d", &(Query[i].x1), &(Query[i].y1), &(Query[i].x2), &(Query[i].y2));
Query[i].x1 -= 2;
Query[i].y1 -= 2;
Query[i].x2--;
Query[i].y2--;
}
for(int i = 0; i < n; i++)
{
PLANT& P = Plant[i];
int d = (P.a - 1) / P.b;
int x1 = P.x - d;
int y1 = P.y - d;
int x2 = P.x + d + 1;
int y2 = P.y + d + 1;
int r = P.a % P.b;
if(r)
{
Nuclearia(max(0, x1), max(0, y1)) += r;
if(x2 < w) Nuclearia(x2, max(0, y1)) -= r;
if(y2 < h) Nuclearia(max(0, x1), y2) -= r;
if((x2 < w) && (y2 < h)) Nuclearia(x2, y2) += r;
x1++;
y1++;
x2--;
y2--;
}
if(P.a >= P.b)
{
UpdatePosDiag(x1, y1, x2, y2, P.b);
UpdateNegDiag(x1, y1, x2, y2, P.b);
}
}
SummarizeDiags();
AddDiags();
SummarizeLines();
AddLines();
Summarize();
Summarize();
for(int i = 0; i < q; i++)
{
QUERY& Q = Query[i];
huge rsl = Nuclearia(Q.x2, Q.y2);
if(Q.x1 >= 0) rsl -= Nuclearia(Q.x1, Q.y2);
if(Q.y1 >= 0) rsl -= Nuclearia(Q.x2, Q.y1);
if((Q.x1 >= 0) && (Q.y1 >= 0)) rsl += Nuclearia(Q.x1, Q.y1);
Print(rsl, (Q.x2 - Q.x1) * (Q.y2 - Q.y1));
}
return 0;
}