二维前缀和详解：从模板到激光炸弹实战

题目二：激光炸弹

这道题在模板基础上增加了枚举最大值的需求。地图上有 n 个目标，每个目标有位置和价值。一颗边长为 R 的正方形炸弹可以摧毁覆盖区域内的所有目标。问一次轰炸能获得的最大价值是多少。

思路分析：

1. 去重处理：同一个坐标可能有多个目标，需要累加价值。
2. 边界判断：如果 R 大于地图最大维度（5000），则可以直接摧毁所有目标。
3. 枚举策略：枚举正方形的右下角坐标 (x2, y2)，根据边长 R 推算出左上角 (x1, y1)，利用前缀和快速计算当前正方形内的总价值，并更新最大值。

代码实现： 注意坐标偏移，题目中坐标可能从 0 开始或存在重复，代码中做了相应的调整以适应前缀和下标习惯。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 5010;
int f[N][N];
int a[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x, y, v;
        cin >> x >> y >> v;
        x++; y++; // 坐标平移，避免 0 下标问题
        a[x][y] += v;
    }
    
    // 限制最大范围
    n = 5001; 
    
    // 构建前缀和
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
    }
    
    int ret = 0;
    m = min(m, n); // 确保边长不超过实际范围
    
    // 枚举所有可能的 R*R 正方形
    for(int x2 = m; x2 <= n; x2++){
        for(int y2 = m; y2 <= n; y2++){
            int x1 = x2 - m + 1;
            int y1 = y2 - m + 1;
            ret = max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]);
        }
    }
    
    cout << ret << endl;
    return 0;
}

小结

掌握二维前缀和的关键在于理解容斥原理在矩阵中的应用。在实际编码时，务必处理好下标越界、数据类型溢出以及坐标映射等细节。这两道题涵盖了基础应用与变体优化，建议动手复现代码以加深理解。