三体人将对地球发起攻击。为了抵御攻击，地球人派出了 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。
A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。
输出
输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。
样例输入
1. 2 2 2 3 2. 1 1 1 1 1 1 1 1 3. 1 2 1 2 1 1 1 4. 1 1 1 2 1 2 1 5. 1 1 1 1 1 1 2
样例输出
2
提示
在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。
思路：
参考大佬的讲解
【2018.10.18】noip模拟赛Day2 地球危机（2018年第九届蓝桥杯C/C++A组省赛 三体攻击） - 大本营 - 博客园 (cnblogs.com)
注意：在扣除一块区域的血量时，相邻点的差分值总是相反的，而（i,j,k)+=k，（i-1,j-1,k-1)+=k。我们在通过差分计算实际血量时(i,j,k)要加上相邻的三个点，减去相隔一个点的点，加上(i-1, j-1, k-1)这个点。
代码：
1. A,B,C,m=map(int,input().split()) 2. ships=[0]#存储舰队血量的数组 3. difference=[]#差分数组，用来存储每个每个传 4. ope=[None]*(m+1) 5. 6. #用一维数组存储三维空间 7. def get(x,y,z): 8. global B,C 9. return ((x-1)*B+(y-1))*C+z 10. 11. #向差分数组扣除血量，实现想要的区域血量减少 12. def diffAdd(x1,x2,y1,y2,z1,z2,c): 13. global difference 14. difference[get(x1 , y1 , z1 )] += c 15. difference[get(x2+1, y1 , z1 )] -= c 16. difference[get(x1 , y2+1, z1 )] -= c 17. difference[get(x1 , y1 , z2+1)] -= c 18. difference[get(x2+1, y2+1, z1 )] += c 19. difference[get(x2+1, y1 , z2+1)] += c 20. difference[get(x1 , y2+1, z2+1)] += c 21. difference[get(x2+1, y2+1, z2+1)] -= c 22. 23. 24. 25. def check(x): 26. global difference,A,B,C 27. difference = [0] * ((A+1)*(B+1)*(C+1)+1) 28. for i in range(1, x+1): 29. diffAdd(ope[i][0], ope[i][1], ope[i][2], ope[i][3], ope[i][4], ope[i][5], ope[i][6]) 30. 31. 32. #计算出每一个飞船的血量，有血量小于零的则返回true 33. for i in range(1, A+1): 34. for j in range(1, B+1): 35. for k in range(1, C+1): 36. difference[get(i,j,k)] += difference[get(i-1, j , k )] 37. difference[get(i,j,k)] += difference[get(i , j-1, k )] 38. difference[get(i,j,k)] += difference[get(i , j , k-1)] 39. difference[get(i,j,k)] -= difference[get(i-1, j-1, k )] 40. difference[get(i,j,k)] -= difference[get(i-1, j , k-1)] 41. difference[get(i,j,k)] -= difference[get(i , j-1, k-1)] 42. difference[get(i,j,k)] += difference[get(i-1, j-1, k-1)] 43. if difference[get(i, j, k)] > ships[get(i, j, k)]: 44. return True 45. return False 46. 47. 48. ships+=list(map(int,input().split())) 49. 50. for i in range(1,m+1): 51. ope[i]=list(map(int,input().split())) 52. 53. #二分法，一共m次攻击，我们要找的数在1~m中 54. L,R=1,m 55. while L<R: 56. mid=(L+R)//2 57. if check(mid): 58. R=mid 59. else : 60. L=mid+1 61. 62. print(R)
