自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 22:56:20，当前版本为作者最后更新于2024-03-23 15:35:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

将每个炸弹拆成若干个以该炸弹为中心的正方形矩形加一个值的形式，二维前缀和即可做到单次操作 $O(n)$。

观察到二维前缀和所需要修改的权值是四个等差数列，如下图：

对两条斜线分别进行二维差分即可维护。时间复杂度为 $O(nm+k)$。

#include"bits/stdc++.h"
using namespace std;
#define int long long
const int maxn = 3010;
const int B = 1010;
const int maxm = 1000100;
int n,m,k,v[maxn][maxn];
int a[maxn][maxn],b[maxn][maxn],Sa[maxn][maxn],Sb[maxn][maxn],S[maxn][maxn];
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>v[i][j];
	for(int i=1,x,y,p;i<=k;i++){
		cin>>x>>y>>p;p--;
		x+=B,y+=B;
		Sa[x-p][y-p]+=1;
		a[x-p+1][y-p+1]+=2;
		a[x+1][y+1]-=2;
		a[x+2][y+2]-=2;
		a[x+p+2][y+p+2]+=2;
		Sa[x+p+2][y+p+2]-=1;
		Sb[x-p][y+p+1]-=1;
		b[x-p+1][y+p]-=2;
		b[x+1][y]+=2;
		b[x+2][y-1]+=2;
		b[x+p+2][y-p-1]-=2;
		Sb[x+p+2][y-p-1]+=1;
	}
	for(int i=1;i<maxn;i++)
		for(int j=1;j<maxn;j++)
			a[i][j]+=a[i-1][j-1];
	for(int i=1;i<maxn;i++)
		for(int j=1;j<maxn;j++)
			Sa[i][j]=Sa[i][j]+a[i][j]+Sa[i-1][j-1];
	for(int i=1;i<maxn;i++)
		for(int j=maxn-2;j>=0;j--)
			b[i][j]+=b[i-1][j+1];
	for(int i=1;i<maxn;i++)
		for(int j=maxn-2;j>=0;j--)
			Sb[i][j]=Sb[i][j]+b[i][j]+Sb[i-1][j+1];
	for(int i=0;i<maxn;i++)
		for(int j=0;j<maxn;j++)
			S[i][j]+=Sb[i][j];
	for(int i=0;i<maxn;i++)
		for(int j=0;j<maxn;j++)
			S[i][j]+=Sa[i][j];
	for(int i=1;i<maxn;i++)
		for(int j=1;j<maxn;j++)
			S[i][j]+=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
	for(int i=1;i<=n;i++,cout<<endl)
		for(int j=1;j<=m;j++)
			cout<<max(0ll,v[i][j]-S[i+B][j+B])<<' ';
}