三体攻击

三维差分

#include<stdio.h>
int A,B,C,n,m;
const int N = 1000005;
int s[N];                               //存储舰队生命值
int D[N];                               //三维差分数组（压维）；同时也用来计算每个点的攻击值
int x2[N], y2[N], z2[N];                //存储区间修改的范围，即攻击的范围
int x1[N], y1[N], z1[N];
int d[N];                               //记录伤害，就是区间修改
int num(int x,int y,int z) {
  //小技巧：压维，把三维坐标[(x,y,z)转为一维的((x-1)*B+(y-1))*C+(z1)+1
  if (x>A || y>B || z>C) return 0;
    return ((x-1)*B+(y-1))*C+(z-1)+1;
}
bool check(int x){                      //做x次区间修改。即检查经过x次攻击后是否有战舰爆炸
  for (int i=1; i<=n; i++) D[i]=0;      //差分数组的初值，本题是0
  for (int i=1; i<=x; i++) {            //用三维差分数组记录区间修改：有8个区间端点
    D[num(x1[i],   y1[i],   z1[i])]    += d[i];
    D[num(x2[i]+1, y1[i],   z1[i])]    -= d[i];
    D[num(x1[i],   y1[i],   z2[i]+1)]  -= d[i];
    D[num(x2[i]+1, y1[i],   z2[i]+1)]  += d[i];
    D[num(x1[i],   y2[i]+1, z1[i])]    -= d[i];
    D[num(x2[i]+1, y2[i]+1, z1[i])]    += d[i];
    D[num(x1[i],   y2[i]+1, z2[i]+1)]  += d[i];
    D[num(x2[i]+1, y2[i]+1, z2[i]+1)]  -= d[i];
  }
  //下面从x、y、z三个方向计算前缀和
  for (int i=1; i<=A; i++)
    for (int j=1; j<=B; j++)
      for (int k=1; k<C; k++)           //把x、y看成定值，累加z方向
        D[num(i,j,k+1)] += D[num(i,j,k)];
  for (int i=1; i<=A; i++)
    for (int k=1; k<=C; k++)
      for (int j=1; j<B; j++)           //把x、z看成定值，累加y方向
        D[num(i,j+1,k)] += D[num(i,j,k)];
  for (int j=1; j<=B; j++)
    for (int k=1; k<=C; k++)
      for (int i=1; i<A; i++)           //把y、z看成定值，累加x方向
        D[num(i+1,j,k)] += D[num(i,j,k)];
  for (int i=1; i<=n; i++)              //最后判断是否攻击值大于生命值
    if (D[i]>s[i])                      //艘战舰毁灭，再用二分法缩小范围找出第一艘毁灭的战舰
      return true;
  return false;
}
int main() {
  scanf("%d%d%d%d", &A, &B, &C, &m);    //层、行、攻击次数
  n = A*B*C;                            //战舰总数
  for (int i=1; i<=n; i++) scanf("%d", &s[i]);     //读生命值
  for (int i=1; i<=m; i++)              //读每次攻击的范围，用坐标表示
    scanf("%d%d%d%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i],&z1[i],&z2[i],&d[i]);
  int L = 1,R = m;                     //经典的二分写法
  while (L<R) {                        //对m进行二分，找到临界值。总共只循环了log(m)次
    int mid = (L+R)>>1;
    if (check(mid)) R = mid;
    else L = mid+1;
  }
  printf("%d\n", R); //打印临界值
  return 0;
}

笔记：节省三维数组的空间使用了压维，将三维数组压缩成一维数组，区间修改需要8个端点记录修改数值，查询三维数组用前缀和的方式得出修改后的数值。查询最值使用二分法减少时间复杂度