{"problem":{"name":"数列前缀和 4","description":{"content":"给定一个 $n$ 行 $m$ 列的矩阵 $a$，有 $q$ 次询问，每次给定 $(u, v)$ 和 $(x, y)$，请你求出： $$(\\sum_{i = u}^x \\sum_{j = v}^y a_{i,j}) \\bmod 2^{64}$$ 也就是求出以 $(u, v)$ 为左上角、$(x,y)$ 为右下角的矩形元素和对 $2^{64}$ 取余数的结果。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3693"},"statements":[{"statement_type":"Markdown","content":"给定一个 $n$ 行 $m$ 列的矩阵 $a$，有 $q$ 次询问，每次给定 $(u, v)$ 和 $(x, y)$，请你求出：\n\n$$(\\sum_{i = u}^x \\sum_{j = v}^y a_{i,j}) \\bmod 2^{64}$$\n\n也就是求出以 $(u, v)$ 为左上角、$(x,y)$ 为右下角的矩形元素和对 $2^{64}$ 取余数的结果。\n\n## Input\n\n**本题单测试点内有多组测试数据**。\n\n输入的第一行是一个整数 $T$，表示数据组数。接下来依次给出每组数据的输入信息：\n\n第一行三个整数，依次表示矩阵的行数 $n$ 和列数 $m$ 以及询问数 $q$。  \n接下来 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。  \n接下来 $q$ 行，每行四个整数，依次为 $u,v,x, y$，表示一组询问。\n\n## Output\n\n为了避免输出过大，对于每组数据，请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。\n\n[samples]\n\n## Background\n\n这次不是数列的问题了。\n\n## Note\n\n### 样例 1 解释\n\n对第一组数据，三次询问的答案依次为 $45,9,16$。其按位异或和为 $52$。\n\n### 数据规模与约定\n\n对全部的测试点，保证 $1 \\leq T \\leq 10$，$1 \\leq n, m \\leq 10^3$，$1 \\leq q \\leq 10^6$，$0 \\leq a_i < 2^{64}$，$1 \\leq u \\leq x \\leq n$，$1 \\leq v \\leq y \\leq m$。\n\n数据保证 $\\sum(n \\times m) \\leq 10^6$，$\\sum q \\leq 10^6$。即输入矩阵的总大小和询问总数均不超过 $10^6$。\n\n### 提示\n如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：\n\n```cpp\ntemplate <class T>\nT getXorSum(T *begin, T *end) {\n  T ret = 0;\n  for (T *it = begin; it != end; ++it) ret ^= *it;\n  return ret;\n}\n```\n这一函数的作用是计算传入数组（包括 `std::vector`）某一左闭右开区间的按位异或和，返回值类型与传入数组的类型相同，调用方法与 `std::sort` 类似，例如，要求数组 $a$ 的 $a_1 \\sim a_n$ 的按位异或和，则调用 `getXorSum(a + 1, a + 1 + n)`，求 $a_0 \\sim a_{n - 1}$ 的按位异或和，则调用 `getXorSum(a, a + n)`。如果 $a$ 是 `std::vector`，则将上述调用代码里的 `a` 均改为 `a.begin()` 即可。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3693","tags":["O2优化","前缀和"],"sample_group":[["2\n3 3 3\n1 2 3\n4 5 6\n7 8 9\n1 1 3 3\n2 1 2 2\n1 2 2 3\n2 2 1\n1 3\n4 6\n2 2 2 2","52\n6"]],"created_at":"2026-03-03 11:09:25"}}