激光炸弹

地图上有 $N$ 个目标，用整数 $X_i,Y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R×R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_i,Y_i,W_i$，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0≤R≤10^9$
$0<N≤10000$
$0≤X_i,Y_i≤5000$
$0≤W_i≤1000$

输入样例

2 1
0 0 1
1 1 1

输出样例

1

解析

一个前缀和的小运用，因为本题只有一个炸弹，所以我们只需要 贪心 选择一个 $R\times R$ 大小区域内的价值总数最高的即可

那么就有一个疑问，如何快速求得一个 $R\times R$ 大小区域的价值总数？小技巧 前缀和，因为你想快速询问某个区域内的价值总数 最快的方式就是先将里面的所有数加起来放到一个点上，这样无论是询问和扩展都只用询问这个点即可。

知道这个方法，接下来的事情就非常简单了，如果当前询问的点并没有超过R，那么直接与答案求最大值，如果当前询问的点长或宽超过了R，那么就将超过的部分在前面截掉，因为我们用的前缀和，所以在截掉这里的计算也十分的便捷。

但这里注意，如果长和宽都超过了R，同时截掉长和宽多出的一部分就会使这两者重叠的一部分被减掉两次，所以在这里处理的时候需要再加上。

详细看代码

#include <cstdio>
#include <cstring>
#include <iostream>

int N, R;

const int Maxn = 5005;
int Map[Maxn][Maxn];

int main() {
	memset(Map, 0, sizeof(Map));
	scanf("%d %d", &N, &R); int mx = 0, my =0;
	for (int i = 1; i <= N; i++) {
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		Map[x + 1][y + 1] += w;
		mx = std::max(mx, x + 1);
		my = std::max(my, y + 1); //因为防止 -1 会变成负数，我这里 +1
	}
	
	for (int i = 1; i <= mx; i++) {
		for (int j = 1; j <= my; j++) {
			Map[i][j] = Map[i - 1][j] + Map[i][j - 1] - Map[i - 1][j - 1] + Map[i][j];
		}
	} //前缀和计算
	
	int ans = 0;
	for (int i = 1; i <= mx; i++) { //四种情况分别讨论
		for (int j = 1; j <= my; j++) {
			if(i <= R && j <= R) ans = std::max(ans, Map[i][j]);
			if(i > R && j <= R) ans = std::max(ans, Map[i][j] - Map[i - R][j]);
			if(i <= R && j > R) ans = std::max(ans, Map[i][j] - Map[i][j - R]);
			if(i > R && j > R) ans = std::max(ans, Map[i][j] - Map[i - R][j] - Map[i][j - R] + Map[i - R][j - R]); //这里要加上重叠的部分 因为减了两次
		}
	} printf("%d\n", ans);
	return 0;
}