标签：5002 int 激光 HNOI2003 MAXN ........... ask P2280 define

前缀和

对于二维前缀和, 令\(b[n][m]\)是\(\sum_{i=1}^n\sum_{j=1}^ma_{ij}\) 的值, 那么因为容斥原理, 有

\[b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]. \]

要是查询\((a,b)..(c,d)\)的话, 式子就是

\[b[c][d]-b[a-1][d]-b[c][b-1]+b[a-1][b-1]. \]

可以画图理解.

类似的, 二维的情况也有差分的情形, 在某个点加1表示在它左边和上面的矩形都+1. 因此, 我们就可以有这样的操作:

...........
...........
...........
....+==-...
....|  |...
....-==+...
...........

一些坑点

1. 需要开一个数组, 注意在覆盖的时候不要出现UB. 尽量可以使用+=.
2. 注意循环的边界要加1.

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 5020
#define F(i, a, b) for(int i=a; i<=b;i++)
#define Fd(i, a, b) for(int i=a;i>=b;i--)
#define b a
int a[MAXN][MAXN];

int ask(int A, int B, int c, int d){
	return (
		b[c][d]-((A-1>=0)?b[A-1][d]:0)-((B-1>=0)?b[c][B-1]:0)+((A-1>=0 && B-1>=0) ? b[A-1][B-1]: 0)
	);
}

signed main(){
	int n, m;
	cin>>n>>m;
	F(i, 1, n){
		int x, y, v; cin>>x>>y>>v;
		a[x][y] = v;
	}
	b[0][0] = a[0][0]; 
	//Undefined Behavior
	F(i, 1, 5002) b[0][i] += b[0][i-1];
	F(i, 1, 5002) b[i][0] += b[i-1][0];
	F(i, 1, 5002) F(j, 1, 5002){
		b[i][j] += b[i][j-1]+b[i-1][j]-b[i-1][j-1];
	}
	// F(i, 0, 5) {
		// F(j, 0, 5) cout<<b[i][j]<<" ";
		// cout<<"\n";
	// }
	int ans = -114514;
	F(i, 0, 5000-m+1) F(j, 0, 5000-m+1) {
		if(i>5001 || j>5001) continue;
		ans = max(ans, ask(i,j,i+m-1,j+m-1));
	}
	cout<<ans<<endl;
	
	
	
	
}

标签：5002,int,激光,HNOI2003,MAXN,...........,ask,P2280,define
From： https://www.cnblogs.com/augpath/p/16867531.html