题解 P8228 【「Wdoi-5」模块化核熔炉】

· · 题解

题解

本题要求我们在一个巨大的六边形网格中执行正六边形范围的加法。但是正六边形加法并不容易。这里先考虑在一个正方形网格当中执行矩形范围的加法。

为了方便，这些图从左往右分别称为 G_1,G_2,G_3。

利用「差分」和「前缀和」的思路。假设我们现在需要进行矩形加法。如 G_1 中，需要对矩形范围内所有格子都加上一个数字 3。按照从上往下的顺序做一次差分，每个格子里的数变为原来的数减去原来它上方的数字，此时变成了 G_2。我们再对 G_2 按照从左往右的顺序做一次差分，每个格子里的数变为原来的数减去原来它左方的数字，此时变成了 G_3。

此时发现，在 G_3 里实际被更新的格子其实只有四个。这样的复杂度是可以承受的。

实际操作的时候，只需要对这四个格子进行操作，可以得到 G_3；再使用差分的逆运算（也就是前缀和），按照从左往右的顺序做一次前缀和，可以得到 G_2；同理，对 G_2 按照从上往下的顺序做一次前缀和，可以得到 G_1。

这么做有个很好的性质：我们可以把若干次区间加操作在 G_3 里执行四个格子的单点加法（减法），在执行完所有操作后，再从更新后的 G_3 推出 G_2 再推出 G_1，就可以极大减小时间复杂度。对于 n\times m 个格子的正方形阵列，执行 q 次区间加法的复杂度即为 \mathcal O(nm+q)。

但是我们要做的是正六边形里的加法啊。但是不着急。因为我们可以发现，在一个正六边形阵列里，可以按照某个方向进行变换，将一个平行四边形区域转化为矩形区域：

因此，这里考虑将给我们的坐标进行坐标转换。

具体而言，我们新建这样两个坐标系。

按照原点的方位，我们分别将它们称呼为左系和右系。先讨论如何将题目给定的坐标系（称呼为标准系）的坐标转换为左系和右系当中点的坐标。假设给定的坐标为 (x_0,y_0,z_0)。

这张图是对一个右系进行矩形变换后的结果。容易发现，在原图当中一个向右倾斜的平行四边形区域，可以被被转化为右系当中的一个矩形。同理，我们可以对左系进行矩形变换：

因此，我们可以将一个六边形网格图中，一个向左倾斜的平行四边形区域的区间加，转化为左系所对应的那个矩形里的一个矩形加。

知道这些，这条题目就非常简单了。现在假设我们需要对原图当中这样一个大的正六边形区域执行加法操作：

那么它可以被转换为这样四个图形之间的拼接：

其中，红色部分代表的是正值，蓝色部分代表的是负值。它可以被转化为两个左系当中的矩形加，以及两个右系当中的矩形加。

记得处理一下矩阵的边界超出左系/右系的情况，那么这题就做完了。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN=800+3;
int n,m,k;
void cnv1(int a,int b,int c,int &x,int &y){  //左系
    x=a-c+n,y=b-a+n;
}
void cnv2(int a,int b,int c,int &x,int &y){  //右系
    x=a-c+n,y=b-c+n;
}
int A[MAXN*2][MAXN*2],B[MAXN*2][MAXN*2];
int main(){
    n=qread(),m=qread(),k=2*n-1;
    up(1,m,i){
        int x=qread(),y=qread(),z=qread(),r=qread(),w=qread();
        int u,v;
        cnv1(x,y,z,u,v);
        A[u][min(k,v+r-1)]-=w,A[max(1,u-r+1)][min(k,v+r-1)]+=w;
        A[u][max(0,v-r  )]-=w,A[min(k+1,u+r)][max(0,v-r  )]+=w;
        cnv2(x,y,z,u,v);
        B[u][min(k,v+r-1)]+=w,B[min(k+1,u+r)][min(k,v+r-1)]-=w;
        B[u][max(0,v-r  )]+=w,B[max(1,u-r+1)][max(0,v-r  )]-=w;
    }
    up(1,k,i) up(1,k,j) A[i][j]+=A[i-1][j];
    up(1,k,i) up(1,k,j) B[i][j]+=B[i-1][j];
    up(1,k,i) dn(k,1,j) A[i][j]+=A[i][j+1];
    up(1,k,i) dn(k,1,j) B[i][j]+=B[i][j+1];
    up(-n+1,n-1,i) dn(n-1,-n+1+abs(i),j){
        int x=0,y=j,z=0,u,v,w=0; if(i<0) z=-i; else x=i;
        cnv1(x,y,z,u,v),w+=A[u][v];
        cnv2(x,y,z,u,v),w+=B[u][v];
        printf("%d ",w);
    }

    return 0;
}