「Wdoi-5」模块化核熔炉
题目背景
为了通过使用核聚变获得能源,守矢神社在旧地狱修建了巨大的核融合控制中心。控制中心形如双层八卦炉,通过各种电路紧密地调控着核融合的精密运行。获得了八咫鸟力量的阿空会在核反应炉的中心点燃神火。
但是正八边形的八卦炉并不利于进行拓展与维护。为了方便地实现电路,河童打算对核控制中心进行模块化改造,以实现核熔炉的维护。具体而言,河童打算将核控制中心设计成由若干个正六边形组成的巨大结构。
![](https://cdn.luogu.com.cn/upload/image_hosting/ohyfxv02.png)
被赋予了神力的阿空可以依次激发其中的一些模块,而这些被激发的模块会快速影响到一定范围内的其他的模块。通过模块间的链接实现能量的产生。
但是因为阿空脑袋空空,由于它已经激发了多次模块,它已经记不清每个模块当中产生的核融合程度了。你能帮帮它吗?
题目描述
核控制中心可以看作由若干个正六边形模块组成的六边形阵列。阵列当中每个模块都可以储存核融合能量(一个非负整数)。左图就是一个核控制中心示意图。
![](https://cdn.luogu.com.cn/upload/image_hosting/78y7b98x.png)
我们使用如下方式对控制中心中每个模块进行标号。
![](https://cdn.luogu.com.cn/upload/image_hosting/9ffz2m5o.png)
以阵列中心为原点延伸出三根射线作为三根轴,每两根轴之间的夹角为 $120\degree$。这三根轴将平面划分为了三个部分。每个模块都可以使用一个三元组 $(x,y,z)$ 描述它的坐标,表示从原点开始按如图所示的 $x,y,z$ 方向各走若干步之后到达的地方。为了防止出现多个坐标表示同一个模块的情况,做出如下规定:原点的坐标为 $(0,0,0)$;对于中心在坐标轴上的模块,它的坐标就是从原点向所在轴走过的距离;对于其他情况,我们将平面划分为了三个区域(如第二张图的红蓝绿三个区域),一个模块的坐标就是沿着它两侧的轴分别需要走的距离。例如模块 $P$ 的坐标为 $(2,4,0)$。容易发现,每个坐标唯一对应一个模块,一个模块唯一对应一个坐标。
同时定义,两个模块的**距离**为从一个模块到另一个模块需要经过模块(包括起点和终点)的最少个数。在第一张图中,红色部分的模块到其中心距离均不超过 $3$,绿色部分的模块到其中心距离均不超过 $3$,而蓝色部分的模块到其中心距离均不超过 $2$。
核控制中心可以视为到达原点距离不超过 $n$ 的模块组成的阵列。现在阿空会执行以下操作 $m$ 次:
- $\colorbox{f0f0f0}{\verb!x y z r k!}$ :激活坐标为 $(x,y,z)$ 的模块。它会使控制中心中到它距离不超过 $r$ 的**所有**的模块的核融合能量增加 $k$。保证 $(x,y,z)$ 在控制中心当中。
现在需要求出,执行完 $m$ 个操作后,每个模块里核融合能量值。
输入输出格式
输入格式
- 第一行共两个正整数 $n,m$,分别表示控制中心的大小、操作个数。
- 接下来 $m$ 行,每行有五个整数 $x_i,y_i,z_i,r_i,k_i$,表示将距离 $(x_i,y_i,z_i)$ 不超过 $r$ 的所有模块的核融合能量增加 $k_i$。
输出格式
- 共一行,若干个整数。按照从左往右从上往下的顺序,依次输出每个模块当中核融合能量值。每两个值之间使用空格隔开。
下图当中的红色箭头展示了「从左往右从上往下」的顺序。
![](https://cdn.luogu.com.cn/upload/image_hosting/vziqfo7l.png)
输入输出样例
输入样例 #1
4 3
0 1 1 3 4
3 0 3 3 3
1 0 0 2 2
输出样例 #1
4 4 4 0 4 4 4 4 3 4 4 4 4 7 3 0 4 4 6 9 3 3 0 4 6 6 5 3 0 0 2 2 3 0 0 0 0
说明
样例 $2$ 见下发的附件 $\textbf{\textit{nuclear2.in/nuclear2.ans}}$。
样例 $3$ 见下发的附件 $\textbf{\textit{nuclear3.in/nuclear3.ans}}$。满足特殊性质 $\text{A}$(见下文)。
样例 $4$ 见下发的附件 $\textbf{\textit{nuclear4.in/nuclear4.ans}}$。满足特殊性质 $\text{B}$(见下文)。
样例 $5$ 见下发的附件 $\textbf{\textit{nuclear5.in/nuclear5.ans}}$。
#### 样例 1 解释
如图所示(所有未标出数字的模块的核融合能量值均为 $0$):
![](https://cdn.luogu.com.cn/upload/image_hosting/6y7bm2eb.png)
按照从左往右、从上往下的顺序依次输出每个数值,即可得到答案。
#### 数据范围及约定
本题共有 $20$ 个测试点,每个测试点 $5$ 分。最终分数为所有测试点分数之和。
$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Task} & \bm{n\le } & \bm{m\le} & \textbf{特殊性质} \cr\hline
1\sim 3 & 10 & 10 & \text{A} \cr\hline
4\sim 7 & 100 & 300 & - \cr\hline
8\sim 10 & 800 & 3\times 10^5 & \text{B} \cr\hline
11\sim 14 & 800 & 3\times 10^5 & \text{A} \cr\hline
15\sim 20 & 800 & 3\times 10^5 & - \cr\hline
\end{array}
$$
**特殊性质** $\textbf{A}$:保证对于第 $i$ 次操作,被激活的模块到控制中心边缘上的模块的距离不小于 $r_i$。
**特殊性质** $\textbf{B}$:保证对于第 $i$ 次操作,被激活的模块均为 $(0,0,0)$。
对于全部数据,保证 $n\le 800$,$m\le 3\times 10^5$,$1\le k_i\le 5\times 10^3$,$1\le r_i\le 10^9$。每次激活的模块都在控制中心里。