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≤10^6,
1≤m≤10^6,
0≤d(i, j, k), ht≤10^9,
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 点伤害，超出其防御力导致爆炸。

题目链接

题目链接

算法思路

简要描述一下题目，就是有A层B行C列个战舰，每次选包含于其中的一块方形区域进行集体扣血，扣hd,扣到0是极限情况不会摧毁，扣到负数会摧毁，问第几次之后第一艘战舰被摧毁。

暴力模拟的方法就不说了，O(mABC),最多m次，每次最差情况ABC个。

学过线段树懒惰标记的同学可能会试着想有没有办法用少量的标记来代替每次更新(rat-lat+1)(rbt-lbt+1)(rct-lct+1)个战舰的血量，然后要查询的时候再一次性递推式地计算出全部的血量，这样的话我们就要减少查询的次数，那我们就很容易想到二分法，答案肯定是在[1,m]之间的，而且这个搜寻过程类似一个单调函数，左侧没有任何飞船爆炸，右侧是有飞船爆炸，所以我们可以二分搜寻[1,m]区间，比如第一次是(m+1)/2，发现飞船爆炸了，那下次肯定往左边搜，如果没有炸就往右边搜。

接下来是难点
前缀和大家都知道，我们经常用它来求一段区间的和，但是这题我们还要学会把它逆过来用，所以就是用差分

先介绍一维的差分
这里有一个数组d
3,5,4,9,7,8,6
为了方便阅读我们假设下标从1开始
现在要将[3,6]区间的数各减去一个2
也就是变成
3,5,2,7,5,6,6
可以看到我们要改4个数，这完全取决于你要改动的区间大小
但是如果我不是每次改完就查询呢，那会不会有更好的办法？

一维差分

我们引入差分数组s,令s[i]=d[i]-d[i-1]
s[1]=d[1]就好了
这样原来d对应的差分数组s就是
3,2,-1,5,-2,1,-2
接下来我们还是将[3,6]区间的数各减去一个2,
思考一下s中哪些数会发生变化，哪些数会保持，这就像一块地中间的一块凹了下去，凹下去的区域就是[3,6]这块，所以高度差会发生变化的，只有s[3]和s[6+1]，也就是s[3]-=2,s[6+1]+=2

这样的话不管我们改多大的区间，每次都只要改两个数，要查询的时候再利用d[1]=s[1],d[2]=d[1]+s[2]。。。像前缀和一样求出更新后的d

但是这题的话,就不像一维数组那么连续了，感觉上选择被攻击的一块方形区域是连续的，但是从i层j列k行到i+1层j列k行中间是跳过了B*C个空间的，所以无法直接转化为一维的连续区间变化来做，所以还要引入接下来的二维，三维的差分。

二维差分

拿二维差分来说，我们假设左上角的方格为(0,0),我们用d[i][j]表示第i行第j列的值，s[i][j]表示这里的差分值，这里就不好用直接相减的方法计算差分的值了，我们需要从它的定义搞起，d[i][j]就表示从[1,1]到[i,j]形成的整个矩形的内部的s之和,也就相当于以s作为基的一种面积,比如i=2,j=2的话,
d[2][2]=s[2][2]+s[2][1]+s[1][1]+s[1][2]
不过我们可以有更快的计算方式
如下图所示



将上面三张图重叠起来

就可以很容易看出
d[3][3]就等于蓝色的面积加上红色的面积减去重叠的面积(绿色的)+s[3][3]
d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+s[i][j]
这只是如何计算d的，那么怎么更新s呢，我们从上面的公式可以看出，d[i][j]是由(i,j-1),(i-1,j-1),(i-1,j)这三个点的值联合求出的

上面是中间区域的d减去2以后区域内s的变化，首先左上角的块的变化量肯定就是它自己的d的变化量，因为比它小的前缀和没有任何变化，并且只要这么做，我们绿色区域内的值就一定是原来的值-2，因为我们遍历的时候实质就是
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
{
d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+s[i][j];
}
可见遍历的顺序一定是从左到右，从上到下，所以要进入绿色区域,(2,2)是必经之路，所以一定是最先更新它的s，然后再是第二行第四列的s加上2，最先遍历到的一定要最先加上，这样当你遍历到(2,4)的时候，会发现左边绿色区域的-2和(2,3)的+2刚好抵消了，也可以直接从公式的角度来看
d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+s[i][j]
比如右下角的d(4,4)它要保持不变，而d(3,4)和d(4,3)没变,d(3,3)-=2
所以变化量就是0+0-(-2)+s[i][j]=0
s[i][j]=-2
综上所述就是区间变化量为h时,设两个顶角为(x1,y1)和(x2,y2),则
d[x1][y1]-=h,
d[x1][y1+1]+=h,
d[x1+1][y1]+=h,
d[x1+1][y1+1]-=h,

三维差分

同理我们就可以继续推出三维的差分公式
d[i][j][k]=d[i-1][j][k]+d[i][j-1][k]+d[i][j][k+1]-(d[i-1][j-1][k]+d[i-1][j][k-1]+d[i][j-1][k-1])+d[i-1][j-1][k-1]+s[i][j][k]
然后用上面同样的方法我们就可以分析出每次要改的8个顶点

回到原题

用上面的方法我们就可以以8m的时间更新m次修改后的差分数组，然后每次以最差为ABC的时间复杂度进行查询，所以结合上面我们说的二分法进行查询就可以做到O(log2m(m+ABC))的复杂度，这是我们每次都从零开始更新s数组情况下的复杂度，但是有种情况就是比如在m/2次没有战舰爆炸，所以下次找3/4m的时候只要接着上次的情况更新就行了，但如果m/2爆炸了，下次找m/4,这个时候你可以考虑给战舰回m/4次的血量或者从0开始m/4次，时间上没区别，而且在上述公式中
d[i][j][k]=d[i-1][j][k]+d[i][j-1][k]+d[i][j][k+1]-(d[i-1][j-1][k]+d[i-1][j][k-1]+d[i][j-1][k-1])+d[i-1][j-1][k-1]+s[i][j][k]
不注意的话i-1可能会出现-1的情况，所以干脆将坐标定义成BCi+Cj+k，避免越界。

还有要注意每次查询要对数组d进行初始化,

知道大概的思路就可以自己慢慢写代码了，能完全自己写完才算是有收获了。

不注意的话i-1可能会出现-1的情况，所以干脆将坐标定义成BCi+C*j+k，避免越界，发现C++运行时间会比C多一倍，所以要卡时间的话还是用C好一点

AC代码

#include<stdio.h>
#include<cstring>
long long d[1030301]={0};
long long  s[1030301]={0};
long long  dir[1000000][6]={0};
long long  hd[1000000]={0};
long long  A,B,C,m;
inline int getindex(int i,int j,int k)
{
	return i*B*C+j*C+k;
}
void update(int index,int &pos)
{
	if(pos)
	{
	s[getindex(dir[index][0],dir[index][2],dir[index][4])]-=hd[index];
    s[getindex(dir[index][1]+1,dir[index][2],dir[index][4])]+=hd[index];
    s[getindex(dir[index][0],dir[index][3]+1,dir[index][4])]+=hd[index];
    s[getindex(dir[index][0],dir[index][2],dir[index][5]+1)]+=hd[index];
    s[getindex(dir[index][1]+1,dir[index][3]+1,dir[index][4])]-=hd[index];
    s[getindex(dir[index][1]+1,dir[index][2],dir[index][5]+1)]-=hd[index];
    s[getindex(dir[index][0],dir[index][3]+1,dir[index][5]+1)]-=hd[index];
    s[getindex(dir[index][1]+1,dir[index][3]+1,dir[index][5]+1)]+=hd[index];
	}
	else
	{
	s[getindex(dir[index][0],dir[index][2],dir[index][4])]+=hd[index];
    s[getindex(dir[index][1]+1,dir[index][2],dir[index][4])]-=hd[index];
    s[getindex(dir[index][0],dir[index][3]+1,dir[index][4])]-=hd[index];
    s[getindex(dir[index][0],dir[index][2],dir[index][5]+1)]-=hd[index];
    s[getindex(dir[index][1]+1,dir[index][3]+1,dir[index][4])]+=hd[index];
    s[getindex(dir[index][1]+1,dir[index][2],dir[index][5]+1)]+=hd[index];
    s[getindex(dir[index][0],dir[index][3]+1,dir[index][5]+1)]+=hd[index];
    s[getindex(dir[index][1]+1,dir[index][3]+1,dir[index][5]+1)]-=hd[index];
	}
}
bool cal()
{
	memset(d,0,sizeof d);
	for(int i=1;i<=A;i++)
		for(int j=1;j<=B;j++)
		{
			int sum=0;
			for(int k=1;k<=C;k++)
			{
				d[getindex(i,j,k)]=d[getindex(i-1,j,k)]+d[getindex(i,j-1,k)]+d[getindex(i,j,k-1)]-
				(d[getindex(i-1,j-1,k)]+d[getindex(i-1,j,k-1)]+d[getindex(i,j-1,k-1)])+d[getindex(i-1,j-1,k-1)]+s[getindex(i,j,k)];
				if(d[getindex(i,j,k)]<0)return false;
			}
		}
	return true;
}
int main()
{
	scanf("%d%d%d%d",&A,&B,&C,&m);
	int x;
	for(int i=1;i<=A;i++)
		for(int j=1;j<=B;j++)
			for(int k=1;k<=C;k++)
			{
				scanf("%d",&x);
				s[getindex(i,j,k)]+=x;
				s[getindex(i+1,j,k)]-=x;
				s[getindex(i,j+1,k)]-=x;
				s[getindex(i,j,k+1)]-=x;
				s[getindex(i,j+1,k+1)]+=x;
				s[getindex(i+1,j,k+1)]+=x;
				s[getindex(i+1,j+1,k)]+=x;
				s[getindex(i+1,j+1,k+1)]-=x;
			}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<6;j++)
			scanf("%d",&dir[i][j]);
		scanf("%d",&hd[i]);
	}

	int l=0,r=m-1;
	int mid=(l+r)/2;
	int pos;
	for(int index=0;index<mid;index++)
	{
		pos=1;
		update(index,pos);
	}
	while(l<r)
	{
		if(cal())
		{
			l=mid+1;
			mid=(l+r)/2;
			for(int index=l-1;index<mid;index++)
			{
				pos=1;
				update(index,pos);
			}
		}
		else
		{
			r=mid;
			mid=(l+r)/2;
			for(int index=mid;index<r;index++)
			{
				pos=0;
				update(index,pos);
			}
		}
	}
	printf("%d",r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110