链接：https://ac.nowcoder.com/acm/problem/20032
来源：牛客网

题目描述

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。 

本题是一道典型的二维差分前缀和的问题。通过对所给数据进行前缀和的计算可以很方便的通过差分求出每一个区域内的数量。通过不断求出每一个区域的数量就可以得到最大的区域。值得注意的是在这里需要通过题目中给的r进行范围上的判断，通过范围来绝对是否要进行差分。
代码如下： 
//题目分析下来是一道二维前缀和的问题
#include <iostream>
#include <cstdio>


using namespace std;
const int MAXN = 10000+10;
const int maxx=5001, maxy = 5001;
int a[MAXN][MAXN];

int main() {
    int n, r, k;
    cin>>n>>r;
    int x, y, val;
    //先读入
    for (int i=1;i<=n;i++) {
        cin>>x>>y>>val;
        a[x+1][y+1] = val;
    }
    //首先以前缀和的形式读入，从一开始读可以保证一致性，不需要对前面的进行特殊判断。
    for (int i=1;i<=maxx;i++) {
        for (int j=1;j<=maxy;j++) {
            //一边读入一边计算前缀和
            a[i][j] = a[i][j-1]+a[i-1][j]-a[i-1][j-1]+a[i][j];
//             cout<<"i="<<i<<" "<<"j="<<j<<" "<<"a[i][j]="<<a[i][j]<<endl;
        }
    }
    int maxn = -1;
    int sum = 0;
    //通过形成的前缀和数组，来快速计算区域内的数值
    for (int i=1;i<=maxx;i++) {
        for (int j=1;j<=maxy;j++) {
//             cout<<"i="<<i<<" "<<"j="<<j<<" "<<"a[i][j]="<<a[i][j]<<endl;
            sum = 0;
            sum += a[i][j];
            if (i-r>0) {
                sum -= a[i-r][j];
            }
            if (j-r>0) {
                sum -= a[i][j-r];
            }
            if (i-r>0&&j-r>0) {
                sum += a[i-r][j-r];
            }
//             cout<<"i="<<i<<" "<<"j="<<j<<" "<<"sum="<<sum<<endl;
            if (sum>maxn) {
                maxn = sum;
            }
        }
    }
    cout<<maxn;
    
    return 0;
}