Bite The Crust

Undead2008 · 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])<<' ';
}