自动搬运

查看原文

来自洛谷，原作者为

	GUO120822 どうしたの？

搬运于2025-08-24 22:41:15，当前版本为作者最后更新于2024-01-10 21:37:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在 12 月 30 日更新。

先看下题目。

• 题目大意

这题其实就是一个修改问题，每次修改一个部分，看第几次有一个战舰累计受到的总伤害超过其防御力，就输出这个攻击的轮数。

• 思路

我们读完题，会发现这道题其实具有单调性。为什么呢？因为操作轮数越多，有某一个船爆炸的概率就越大。所以可以二分答案。

l=1;
r=m;
while (l<=r)
{
    mid=l+r>>1;
    if (check(mid)) r=mid-1;
    else l=mid+1;
}

那么怎么检查呢？这就用到了三维差分。

三维差分怎么做？我们先来看看一维和二维的我们是怎么做的。

一维：

a[s]+=h;
a[t+1]-=h;

二维（奇减偶加）：

b[sx][sy]+=h;
b[sx][ty+1]-=h;
b[tx+1][sy]-=h;
b[tx+1][ty+1]+=h;

由此，我们根据容斥原理，发现三维的是奇加偶减，可得三维差分公式：

c[calc(sx,sy,sz)]+=h;
c[calc(tx+1,sy,sz)]-=h;
c[calc(sx,ty+1,sz)]-=h;
c[calc(sx,sy,tz+1)]-=h;
c[calc(sx,ty+1,tz+1)]+=h;
c[calc(tx+1,sy,tz+1)]+=h;
c[calc(tx+1,ty+1,sz)]+=h;
c[calc(tx+1,ty+1,tz+1)]-=h;

在做完差分后，再求前缀和（容斥原理，奇加偶减）。

c[calc(i,j,k)]+=
c[calc(i-1,j,k)]
+c[calc(i,j-1,k)]
+c[calc(i,j,k-1)]
-c[calc(i-1,j-1,k)]
-c[calc(i-1,j,k-1)]
-c[calc(i,j-1,k-1)]
+c[calc(i-1,j-1,k-1)];

计算函数指的是把三维压成一维，映射它在一维数组中的位置。

int calc(int a,int b,int c)
{
    return max(0ll,((a-1)*B+(b-1))*C+(c-1)+1);
    			|
          防越界
}

最后，展示。

注意 HACK 数据。

• 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int A,B,C,m,i,j,k,a[N],c[N];
int sx[N],sy[N],sz[N],tx[N],ty[N],tz[N],h[N];
int l,r,mid;
int calc(int a,int b,int c)
{
	return max(0ll,((a-1)*B+(b-1))*C+(c-1)+1);
}
void cf(int sx,int sy,int sz,int tx,int ty,int tz,int h)
{
	c[calc(sx,sy,sz)]+=h;
	c[calc(tx+1,sy,sz)]-=h;
	c[calc(sx,ty+1,sz)]-=h;
	c[calc(sx,sy,tz+1)]-=h;
	c[calc(sx,ty+1,tz+1)]+=h;
	c[calc(tx+1,sy,tz+1)]+=h;
	c[calc(tx+1,ty+1,sz)]+=h;
	c[calc(tx+1,ty+1,tz+1)]-=h;
}
bool check(int mid)
{
	memset(c,0,sizeof(c));
	int i,j,k;
	for (i=1;i<=mid;i++) cf(sx[i],sy[i],sz[i],tx[i],ty[i],tz[i],h[i]);
	for (i=1;i<=A;i++)
	{
		for (j=1;j<=B;j++)
		{
			for (k=1;k<=C;k++)
			{
				c[calc(i,j,k)]+=
    			c[calc(i-1,j,k)]
    			+c[calc(i,j-1,k)]
    			+c[calc(i,j,k-1)]
    			-c[calc(i-1,j-1,k)]
    			-c[calc(i-1,j,k-1)]
    			-c[calc(i,j-1,k-1)]
    			+c[calc(i-1,j-1,k-1)];
				if (c[calc(i,j,k)]>a[calc(i,j,k)]) return true; 
			}
		}
	}
	return false;
}
signed main()
{
	scanf("%lld%lld%lld%lld",&A,&B,&C,&m);
	for (i=1;i<=A;i++)
	{
		for (j=1;j<=B;j++)
		{
			for (k=1;k<=C;k++) scanf("%lld",&a[calc(i,j,k)]);
		}
	}
	for (i=1;i<=m;i++) scanf("%lld%lld%lld%lld%lld%lld%lld",&sx[i],&tx[i],&sy[i],&ty[i],&sz[i],&tz[i],&h[i]);
	l=1;
	r=m;
	while (l<=r)
	{
		mid=l+r>>1;
		if (check(mid)) r=mid-1;
		else l=mid+1;
	}
	printf("%lld",l);
	return 0;
}