三体攻击(蓝桥杯省赛2018C/C++A组第七题) 前缀和与差分优化

题目：

题目描述：略

输入输出样例

示例

输入

2 2 2 3

1 1 1 1 1 1 1 1

1 2 1 2 1 1 1

1 1 1 2 1 2 1

1 1 1 1 1 1 2

输出

2

思路：

前置知识：**[前缀和与差分上](https://blog.csdn.net/weixin_40934238/article/details/122814928)**、[**前缀与差分下**](https://blog.csdn.net/weixin_40934238/article/details/122828332)

三维前缀和公式：

S(x,y,z) = b(x,y,z) + S(x-1,y,z) + S(x,y-1,z) - S(x-1,y-1,z) + S(x,y,z-1) - S(x-1,y,z-1) - S(x,y-1,z-1) + S(x-1,y-1,z-1)

方便记忆：
S(X,Y,Z)括号里面的"-"位置由二进制的"1"位置决定
加减运算符号由二进制总数"1"决定，若为奇数就(+)、为偶数就(-)

S(X, Y, Z) = a(X, Y, Z) + 表示
001 符号：+ S(X, Y, Z - 1)
010 符号：+ S(X, Y - 1, Z)
011 符号：- S(X, Y - 1, Z - 1)
100 符号：+ S(X - 1, Y, Z)
101 符号：- S(X - 1, Y, Z - 1)
110 符号：- S(X - 1, Y - 1, Z)
111 符号：+ S(X - 1, Y - 1, Z - 1)

三维差分操作给(x1,y1,z1) 到 (x2,y2,z2) 加 h

void insert(int x1,int y1,int z1,int x2,int y2,int z2,int h)
{//对b数组执行插入操作，等价于对a数组中的(x1,y1,z1)到(x2,y2,z2)之间的元素都加上了h
    b(x1, y1, z1) +=h
b(x1, y1, z2+1) -=h
b(x1, y2+1, z1) -=h
b(x1, y2+1, z2+1) +=h
b(x2+1, y1, z1) -=h
b(x2+1, y1, z2+1) +=h
b(x2+1, y2+1, z1) +=h
b(x2+1, y2+1, z2+1) -=h
}

代码：

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=2e6+10;

int A,B,C,m;// 声明第一行参数, A层 B行 C列 m轮攻击
LL s[N],b[N],bS[N];// 声明战舰防御值数组、差分数组、前缀和数组

// 定义存放每轮攻击的7个参数结构体
struct Atk{
    int x1,y1,z1,x2,y2,z2,h;
}atk[N];

// 三维转为一维表示
int getindex(int i,int j,int k){
    return ((i - 1)*B + (j -1))*C + k;
}

// 三维差分操作
void insert(LL b[],int x1,int y1,int z1,int x2,int y2,int z2,int h){
    b[getindex(x1,y1,z1)] += h;
    b[getindex(x1,y1,z2+1)] -= h;
    b[getindex(x1,y2+1,z1)] -= h;
    b[getindex(x1,y2+1,z2+1)] += h;
    b[getindex(x2+1,y1,z1)] -= h;
    b[getindex(x2+1,y1,z2+1)] += h;
    b[getindex(x2+1,y2+1,z1)] += h;
    b[getindex(x2+1,y2+1,z2+1)] -= h;
}

// 检查是否爆炸函数
    // 将1~t轮攻击进行差分操作
    // 进行前缀和操作并判断
int check(int t){
    memcpy(bS,b,sizeof(bS));//将b赋值给bS
    
    for(int i=1;i <= t;i++){
        //构造差分函数
        insert(bS,atk[i].x1,atk[i].y1,atk[i].z1,atk[i].x2,atk[i].y2,atk[i].z2,atk[i].h);
    }

    for(int i = 1;i <= A;i++){
        for(int j = 1;j <= B;j++){
            for(int k = 1; k <= C; k++){//前缀和操作
                bS[getindex(i,j,k)] += bS[getindex(i,j,k -1)];
                bS[getindex(i,j,k)] += bS[getindex(i,j-1,k)];
                bS[getindex(i,j,k)] -= bS[getindex(i,j-1,k -1)];
                bS[getindex(i,j,k)] += bS[getindex(i-1,j,k)];
                bS[getindex(i,j,k)] -= bS[getindex(i-1,j,k -1)];
                bS[getindex(i,j,k)] -= bS[getindex(i-1,j-1,k)];
                bS[getindex(i,j,k)] += bS[getindex(i-1,j-1,k -1)];
                // cout<<bS[getindex(i,j,k)]<<endl;
                if(bS[getindex(i,j,k)] < 0){
                    return 1;
                }
            }
        }
    }
    return 0;
}


int main()
{
    cin>>A>>B>>C>>m;
    
    // 给大立方体的每个小方格赋值给防御值的同时初始化差分数组
    for(int i = 1;i <= A;i++){
        for(int j = 1;j <= B;j++){
            for(int k = 1; k <= C; k++){
                cin>>s[getindex(i,j,k)];//将三维坐标转为一维数组，同时初始化给防御值数组s[N]
                insert(b,i,j,k,i,j,k,s[getindex(i,j,k)]);
            }
        }
    }
    
  
    // 接收每次攻击时的7个参数
    for(int i=1; i <= m;i++){
        int x1,y1,z1,x2,y2,z2,h;
        //该死，这输入顺序bug调了半天
        cin>>x1>>x2>>y1>>y2>>z1>>z2>>h;
        atk[i] = {x1,y1,z1,x2,y2,z2,-h};
    }
    
    // 二分法进行判断是否爆炸
    int l=1,r=m;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid + 1;
        }
        
    }
    std::cout << l << std::endl;//最后l是等于r 
    return 0;
}

知识点总结：

     1. 三维前缀和

     2. 三维差分操作

     3. 二分查找