题目
题目描述
核能国可以看作一个由$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}$。
输出格式
对于每个询问，输出一行表示给定矩形区域内所有方格的平均辐射量，四舍五入至整数。
样例
样例输入
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- $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}$时，它才会受影响
所以，我们只需要枚举这个核电站的势力范围就可以了
//官方程序
#include <stdio.h>
#include <stdlib.h>
#define MAXWH 10000000
#define MAXN 1000000
#define MAXQ 1000000
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)$
//官方程序
#include <stdio.h>
#include <stdlib.h>
#define MAXWH 10000000
#define MAXN 1000000
#define MAXQ 1000000
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$，存储超出边界的部分，具体的实现就看程序吧，这些细节的处理，这里就不再细讲了//官方程序 #include <stdio.h> #include <stdlib.h>
#define MAXWH 10000000
#define MAXN 1000000
#define MAXQ 1000000
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;}
```
喜欢的话，给博主赏一杯冰阔乐吧~
 |
|
|
