题解：P8666 [蓝桥杯 2018 省 A] 三体攻击
P8666 [蓝桥杯 2018 省 A] 三体攻击 细节诠释
真的实在找不到哪里的LaTeX格式有问题了（
本题的主要思路是 三维差分 + 二分优化 + 压维，这篇题解主要是对一些概念做出解释，希望想理解这题做法的人能一遍看懂，然后码字一遍过。
三维差分
差分是什么？可以理解为前缀和的逆运算。我们用前缀和来获取前几个元素的和，差分则是反过来，用前缀和获取第几个元素的和。差分适合区间修改和单次的查询。
区间修改范围为
[4,6] ， ST 指刚进入修改区间的线，终点坐标为4 ， ED 指刚离开修改区间的线，终点坐标为7 。
我们先从一维差分开始。我们想象一条线出来，我们随便给线上一段染色，同时，我们从这条线的起点再平行拉一条新的线。染色对应的是刚才提到的区间修改，拉的线代表差分数组的前缀和，而我们的目的就是修改一个差分数组来让这个数组的前缀和能代表第几个元素的值。我们可以发现，当我们的线刚拉到染色那一段的时候，我们这条线的终点就来到了染色的地方，这个时候终点元素的值就被修改区间的时候修改了，于是，我们需要修改刚好进入区间的那个元素（区间的头），在这里加区间修改的值。然后我们刚好拉出染色那一段时，线的终点过了染色区，终点元素不在这个区间修改的范围了，于是，我们需要修改在刚好走出区间的那个元素（区间的尾
橙色代表差分数组前缀和，绿色代表修改区间（线是方便定位坐标拉的），蓝色代表加的点，紫色代表减的点，褐色代表差分数组前缀和与修改区间的重叠部分。
其次我们来到了二维，我们的染色变成了一个平面，我们拉线也变成了从起点拉一个矩形出来。跟一维一样，我们需要保证我们的差分数组的前缀和（此处是一个矩形，一维是条线），在进入修改区间（这里是一个矩形）要加上区间修改的值，在刚好走出去区间时要减去区间修改的值。但是我们发现，当我们拉出来的矩形在刚好完全覆盖这个矩形后，减了两次区间修改的值，却增加了一次。那我们后面统计前缀和的同时，就永远减去了这个区间修改的值。这如何是好？我们便仿照刚才刚好出区间减区间值，在刚好完全覆盖区间并走出去时，加上区间值来补偿之前多减的一次。我们补偿的地方同样是这个区间的外面。还是与半开区间
绿色代表修改区间，橙色代表差分数组前缀和，蓝色是加的点（用一个立方体代替了），紫色是减的，最后两个图叠在一起就是总共要改的点。
最后我们升维到三维空间，我们有更多的点需要修改，这如何是好？其实我们只需要仿照刚才推理的过程，从起点拉一个立方体作为差分数组的前缀和，当我们进入修改区间（也是一个空间内的立方体）时，我们加上区间修改值；刚好走出去时，减去区间修改值。我们从不同方向
整理下我们得到三维修改区间时要改的差分数组的位置。
// d 是差分数组， d 的前缀和代表第几个元素的值
// findit 是我的压维函数，可以暂时不用理，后面 xyz 是坐标，理解成 d[x][y][z] 就行
//x1,y1,z1是代表修改区间的立方体中最靠近起始点的端点
//x2,y2,z2是代表修改区间的立方体中最远离起始点的端点
d[findit(x1[i],y1[i],z1[i])]+=h[i];
d[findit(x2[i]+1,y1[i],z1[i])]-=h[i];
d[findit(x1[i],y2[i]+1,z1[i])]-=h[i];
d[findit(x2[i]+1,y2[i]+1,z1[i])]+=h[i];
d[findit(x1[i],y1[i],z2[i]+1)]-=h[i];
d[findit(x2[i]+1,y1[i],z2[i]+1)]+=h[i];
d[findit(x1[i],y2[i]+1,z2[i]+1)]+=h[i];
d[findit(x2[i]+1,y2[i]+1,z2[i]+1)]-=h[i];到这里我们就理解了三维差分的修改逻辑了。当我们得到一个修改区间时，我们把差分数组中它的八个修改点都进行区间值的加加减减就行，然后我们进入统计前缀和。
一维的前缀和很好理解，就是从起点到终点，不断把前一个值往后面加，
但是我们还有另一种方法，我们类推一维前缀和中，将前一个值不断往后加。我们想到：先把一个方向的值往后不断累加，再从另一个方向把值不断累加。接下来举个例子。
原二维数组。
| 1 | 1 | 1 |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | 1 |
横向累加。
| 1 | 2 | 3 |
|---|---|---|
| 1 | 2 | 3 |
| 1 | 2 | 3 |
纵向累加。
| 3 | 6 | 9 |
|---|---|---|
| 2 | 4 | 6 |
| 1 | 2 | 3 |
如何？二维我们姑且可以直接用面积推导公式，但是三维的时候，想用公式推前缀和会比较麻烦。我们就可以用这样把方向拆分，分开累加的方式，三维无非就是多了一个方向而已，代码实现大概如下。
// d 是差分数组，findit 差分数组可忽略，ijk 分别对应 xyz
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
for(int k=2;k<=C;k++)
d[findit(i,j,k)]+=d[findit(i,j,k-1)];
for(int i=1;i<=A;i++)
for(int k=1;k<=C;k++)
for(int j=2;j<=B;j++)
d[findit(i,j,k)]+=d[findit(i,j-1,k)];
for(int j=1;j<=B;j++)
for(int k=1;k<=C;k++)
for(int i=2;i<=A;i++)
d[findit(i,j,k)]+=d[findit(i-1,j,k)];总结下，我们通过修改八个端点来实现区间修改投射到差分数组的修改，通过分开方向递推累加实现了统计前缀和。
二分优化
我们可以发现舰队攻击造成伤害只会越来越多，而题目要我们找一个临界点，刚好有舰队炸了的临界点。
我们先明确我们区间的定义。
$mid$ 次攻击时如果存在舰队爆炸，则 $mid$ 及之后攻击都存在舰队爆炸，根据 $[1,R]$ 的定义，$R=mid-1$。 $mid$ 次攻击时如果不存在舰队爆炸，则 $mid$ 及之前攻击都不存在舰队爆炸，根据 $[L,m]$ 的定义，$R=mid+1$。 题目要我们找刚好舰队炸了的临界点，则 $L$ 刚好是这个临界点，$L$ 就是我们的答案，也可以是 $R+1$。
我们通过明确的定义将二分区间
如果你还想对二分的细节有更多了解可以学习这篇（不是广告，推荐好文）。
int L=1,R=m;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)) R=mid-1;//check为true代表存在舰队爆炸
else L=mid+1;
}
printf("%d\n",L);如果你习惯半开半闭（
while(L<R){
int mid=(L+R)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
printf("%d\n",R);压维
蒟蒻码完题解才发现原来题目有给压维的公式，哭了。
我们发现题目
例如
int findit(int x,int y,int z){
if(x>A or y>B or z>C) return 0;
return (x-1)*B*C+(y-1)*C+(z-1)+1;//细节-1。
//(+1是因为我喜欢下标从1开始，如果你从0开始可不写)
}具体代码可以参考其他题解，都大差不差。理解思路是最主要的。
这里就剧终了，谢谢观看。
Cuxhin、初心