自动搬运

查看原文

来自洛谷，原作者为

	onlyfiee running

搬运于2025-08-24 21:14:26，当前版本为作者最后更新于2023-03-14 16:29:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

update

修改了笔误。

题意

其实就是带权矩阵的总权。

思路

首先我们来了解这道题的解决方法的思路:

定义 $sum_{i,j}$ 是指 $(1,1)$ 到 $(i,j)$ 的前缀和，不难得到：

$$ sum_{i,j}=a+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1} $$

其中 $a$ 是指 $(i,j)$ 的值。如果不懂的话可以自己画个图，因为加的时候 $sum_{i-1,j}+sum_{i,j-1}$ 重复添加了 $sum_{i-1,j-1}$，所以减去。

例如下图，比如我们要求 $(c,b)$ 到 $(d,a)$ 的值：

很容易想到用 $(d,a)$ 减去 $(c,b)$ 的前缀和。

查询

剩下的就是查询了，这个可通过我们之前预处理的 $sum$ 数组来进行查询：

$$ ans=sum_{i,j}+sum_{u-1,v-1}-sum_{u-1,j}-sum_{i,v-1} $$

$u-1,v-1$ 是因为我们 $sum_{i,j}$ 是指 $(1,1)$ 到 $(i,j)$，既然要查询 $(u,v),(i,j)$ 中的值，根据我们预处理的思想，这个自然不难解决。

tips：一定要自己好好想下，还是比较容易处理的。

细节

解决维护和查询的问题后，这道题目并没有解决因为有这样几句话：

请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。

也就是求出以 $(u,v)$ 为左上角、$(x,y)$ 为右下角的矩形元素和对 $2^{64}$ 取余数的结果。

连开 long long 都过不了，要开 unsigned int long long 具体坑点请看代码。

code

#include<bits/stdc++.h>
#define int unsigned long long//一定要开 unsigned long long
using namespace std;
int sum[2050][2050],temp,n,m,q,ans;
int u,v,x,y;
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
      ans=0; //多测不清空，爆零两行泪
	   cin>>n>>m>>q;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)	
			{
			    cin>>temp;
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+temp;
			}//O(nm)预处理
		for(int i=1;i<=q;i++) 
		{
			cin>>u>>v>>x>>y;
			ans^=sum[x][y]+sum[u-1][v-1]-sum[u-1][y]-sum[x][v-1];// O(1)查询
		}//异或处理答案，不取模是因为 unsigned long long 会自然溢出
		cout<<ans<<endl; //记得换行
	}
	return 0;
}