打卡信奥刷题（382）用C++信奥B3693[普及组/提高] 数列前缀和 4

数列前缀和 4

题目背景

这次不是数列的问题了。

题目描述

给定一个 n n n 行 m m m 列的矩阵 a a a，有 q q q 次询问，每次给定 ( u , v ) (u, v) (u,v) 和 ( x , y ) (x, y) (x,y)，请你求出：

( ∑ i = u x ∑ j = v y a i , j )   m o d   2 64 (\sum_{i = u}^x \sum_{j = v}^y a_{i,j}) \bmod 2^{64} (i=u∑x​j=v∑y​ai,j​)mod264

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

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数 T T T，表示数据组数。接下来依次给出每组数据的输入信息：

第一行三个整数，依次表示矩阵的行数 n n n 和列数 m m m 以及询问数 q q q。
接下来 n n n 行，每行 m m m 个整数。第 i i i 行第 j j j 个整数表示 a i , j a_{i,j} ai,j​。
接下来 q q q 行，每行四个整数，依次为 u , v , x , y u,v,x, y u,v,x,y，表示一组询问。

输出格式

为了避免输出过大，对于每组数据，请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。

样例 #1

样例输入 #1

2
3 3 3
1 2 3
4 5 6
7 8 9
1 1 3 3
2 1 2 2
1 2 2 3
2 2 1
1 3
4 6
2 2 2 2

样例输出 #1

52
6

提示

样例 1 解释

对第一组数据，三次询问的答案依次为 45 , 9 , 16 45,9,16 45,9,16。其按位异或和为 52 52 52。

数据规模与约定

对全部的测试点，保证 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10， 1 ≤ n , m ≤ 1 0 3 1 \leq n, m \leq 10^3 1≤n,m≤103， 1 ≤ q ≤ 1 0 6 1 \leq q \leq 10^6 1≤q≤106， 0 ≤ a i < 2 64 0 \leq a_i < 2^{64} 0≤ai​<264， 1 ≤ u ≤ x ≤ n 1 \leq u \leq x \leq n 1≤u≤x≤n， 1 ≤ v ≤ y ≤ m 1 \leq v \leq y \leq m 1≤v≤y≤m。

数据保证 ∑ ( n × m ) ≤ 1 0 6 \sum(n \times m) \leq 10^6 ∑(n×m)≤106， ∑ q ≤ 1 0 6 \sum q \leq 10^6 ∑q≤106。即输入矩阵的总大小和询问总数均不超过 1 0 6 10^6 106。

提示

如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：

template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}

这一函数的作用是计算传入数组（包括 std::vector）某一左闭右开区间的按位异或和，返回值类型与传入数组的类型相同，调用方法与 std::sort 类似，例如，要求数组 a a a 的 a 1 ∼ a n a_1 \sim a_n a1​∼an​ 的按位异或和，则调用 getXorSum(a + 1, a + 1 + n)，求 a 0 ∼ a n − 1 a_0 \sim a_{n - 1} a0​∼an−1​ 的按位异或和，则调用 getXorSum(a, a + n)。如果 a a a 是 std::vector，则将上述调用代码里的 a 均改为 a.begin() 即可。

C++实现

#include<bits/stdc++.h>
#define int 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;
}
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];
}
cout<<ans<<endl;
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容