三体人将对地球发起攻击。
为了抵御攻击，地球人派出了 A×B×C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。
其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i,j,k)）的生命值为 d(i,j,k)。
三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。
具体地，第 t 轮攻击用 7 个参数 lat,rat,lbt,rbt,lct,rct,ht 描述；
所有满足 i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct] 的战舰 (i,j,k) 会受到 ht 的伤害。
如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。
地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。
输入格式
第一行包括 4 个正整数 A,B,C,m；
第二行包含 A×B×C 个整数，其中第 ((i−1)×B+(j−1))×C+(k−1)+1 个数为 d(i, j, k)；
第 3 到第 m+2 行中，第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。
输出格式
输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。
保证一定存在这样的战舰。
数据范围
1≤A×B×C≤106,
1≤m≤106,
0≤d(i, j, k), ht≤109,
1≤lat≤rat≤A,
1≤lbt≤rbt≤B,
1≤lct≤rct≤C
层、行、列的编号都从 1 开始。
输入样例：
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
样例解释
在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸
题解分析：
前置知识：
三维前缀和公式：
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)
三维差分操作 给(x1,y1,z1) 到 (x2,y2,z2) 加 h，插入操作 ：
void insert(LL b[],int x1,int x2,int y1,int y2,int z1,int z2,int c) //三维差分操作
{
b[get(x1, y1, z1)] += c;
b[get(x1, y1, z2+1)] -= c;
b[get(x1, y2+1, z1)] -= c;
b[get(x1, y2+1, z2+1)] += c;
b[get(x2+1, y1, z1)] -= c;
b[get(x2+1, y1, z2+1)] += c;
b[get(x2+1, y2+1, z1)] += c;
b[get(x2+1, y2+1, z2+1)] -= c;
}
ac代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2000010;
int A,B,C,m;
LL s[N],b[N],bp[N];
struct Op
{
int x1,x2,y1,y2,z1,z2,h;
}op[N];
int get(int i,int j,int k)
{
return ((i-1)*B+(j-1))*C+k;
}
void insert(LL b[],int x1,int x2,int y1,int y2,int z1,int z2,int c) //三维差分操作
{
b[get(x1, y1, z1)] += c;
b[get(x1, y1, z2+1)] -= c;
b[get(x1, y2+1, z1)] -= c;
b[get(x1, y2+1, z2+1)] += c;
b[get(x2+1, y1, z1)] -= c;
b[get(x2+1, y1, z2+1)] += c;
b[get(x2+1, y2+1, z1)] += c;
b[get(x2+1, y2+1, z2+1)] -= c;
}
bool check(int t)
{
memcpy(bp,b,sizeof(bp));
for(int i=1; i<=t; ++i){ //操作
insert(bp,op[i].x1,op[i].x2,op[i].y1,op[i].y2,op[i].z1,op[i].z2,op[i].h);
}
for(int i=1; i<=A; ++i){
for(int j=1; j<=B; ++j){
for(int k=1; k<=C; ++k){ //三维前缀和
bp[get(i,j,k)]+=bp[get(i-1, j, k)];
bp[get(i,j,k)]+=bp[get(i, j-1, k)];
bp[get(i,j,k)]-=bp[get(i-1, j-1, k)];
bp[get(i,j,k)]+=bp[get(i, j, k-1)];
bp[get(i,j,k)]-=bp[get(i-1, j, k-1)];
bp[get(i,j,k)]-=bp[get(i, j-1, k-1)];
bp[get(i,j,k)]+=bp[get(i-1, j-1, k-1)];
if(bp[get(i,j,k)]<0){
return true;
}
}
}
}
return false;
}
int main()
{
scanf("%d%d%d%d", &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){
scanf("%lld", &s[get(i,j,k)]);
insert(b,i,i,j,j,k,k,s[get(i,j,k)]);
}
}
}
for(int i=1; i<=m; ++i)
{
int x1,x2,y1,y2,z1,z2,h;
scanf("%d%d%d%d%d%d%d", &x1,&x2,&y1,&y2,&z1,&z2,&h);
op[i] = {x1,x2,y1,y2,z1,z2,-h};
}
int l = 1, r = m;
while(l<r){
int mid = l + r >> 1;
if(check(mid))//如果有爆炸的,往左继续找
r = mid;
else l = mid+1;//如果没有爆炸的，往右找
}
printf("%d\n",l);
return 0;
}
