前缀和&二维前缀和

前缀和&二维前缀和

一维前缀和：没什么好讲的。

二维前缀和：

设 $f_{i,j}$ 表示左上角为 $(0,0)$，右下角为 $(i,j)$ 的矩阵中所有数的和，则根据容斥原理，$f_{i,j}=a_{i,j}+f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1}$。如图所示：

查询的时候同理，设查询 $(x_1,y_1)$ 到 $(x_2,y_2)$ 间所有数的和，则答案为 $f_{x_2,y_2}-f_{x_1-1,y_2}-f_{x_2,y_1-1}+f_{x_1-1,y_1-1}$。

代码：

#include<bits/stdc++.h>
using namespace std;
unsigned int n,m,q,A,B,C;
unsigned long long a[2005][2005],ans;
inline unsigned int rng61() {
	A ^= A << 16;
	A ^= A >> 5;
	A ^= A << 1;
	unsigned int t = A;
	A = B;
	B = C;
	C ^= t ^ A;
	return C;
}
int main(){
	cin>>n>>m>>q>>A>>B>>C;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] = rng61();
			a[i][j]+=(a[i][j-1]+a[i-1][j]-a[i-1][j-1]);
		}
	}
	for (int i = 1; i <= q; i++) {
		int x1 = rng61() % n + 1, x2 = rng61() % n + 1;
		int y1 = rng61() % m + 1, y2 = rng61() % m + 1;
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
		ans^=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
	}
	cout<<ans;
	return 0;
}