AcWing 1232. 三体攻击
三体人将对地球发起攻击。
为了抵御攻击，地球人派出了 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 点伤害，超出其防御力导致爆炸。
我们该如何去解决这个问题呢，首先对一定体积的增减h的操作，我们用差分来搞定，我们又如何去找到第一个出现-1的时刻呢，我们采用二分的方法去找第一个出现-1的时刻。
其实三维的差分以及差分的处理与还原是相当很有难度的，我建议先看y总的视频再入手一下这道题，这道题确实很有难度。
y总的视频
我的代码如下
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef long long LL;const int N=2e6+10;LL s[N],b[N],bp[N];
int op[N][7];
int A,B,C;
int m; int nex[8][4]=
{
{
0,0,0,1},{
0,0,-1,-1},{
0,-1,0,-1},{
-1,0,0,-1},{
0,-1,-1,1},{
-1,0,-1,1},{
-1,-1,0,1},{
-1,-1,-1,-1}
};int get_id(int x,int y,int z)
{
return (x*B+y)*C+z;
}bool check(int mid)
{
memcpy(bp,b,sizeof bp);for(int i=1;i<=mid;i++){
int x1=op[i][0],x2=op[i][1],y1=op[i][2],y2=op[i][3],z1=op[i][4],z2=op[i][5],h=op[i][6];bp[get_id(x1,y1,z1)]-=h;bp[get_id(x1,y1,z2+1)]+=h;bp[get_id(x1,y2+1,z1)]+=h;bp[get_id(x2+1,y1,z1)]+=h;bp[get_id(x1,y2+1,z2+1)]-=h;bp[get_id(x2+1,y1,z2+1)]-=h;bp[get_id(x2+1,y2+1,z1)]-=h;bp[get_id(x2+1,y2+1,z2+1)]+=h;}memset(s,0,sizeof s);for(int i=1;i<=A;i++)for(int j=1;j<=B;j++)for(int z=1;z<=C;z++){
LL &v=s[get_id(i,j,z)];v=bp[get_id(i,j,z)];for(int u=1;u<8;u++)v-=s[get_id(i+nex[u][0],j+nex[u][1],z+nex[u][2])]*nex[u][3];if(v<0)return true;}return false;
}
int main(void)
{
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_id(i,j,k)]);LL &v=b[get_id(i,j,k)];for(int u=0;u<8;u++)v+=s[get_id(i+nex[u][0],j+nex[u][1],k+nex[u][2])]*nex[u][3];}for(int i=1;i<=m;i++)for(int j=0;j<7;j++)scanf("%d",&op[i][j]);int l=1,r=m;while(l<r){
int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}printf("%d",r);return 0;
}