CF2273C Matrix Puzzle

Camila 和 Daniel 是墨西哥最顶尖的解谜对手。多年来，他们一直在国内挑战彼此解决最难的数字游戏，现在他们把目光转向了你。你想向他们证明你也可以在同样的水平竞技，所以他们给你出了如下问题。 给定两个大小为 $n \times n$ 的方阵 $a$ 和 $b$。矩阵的子矩阵 $(r_1, c_1, r_2, c_2)$ 指的是从第 $r_1$ 行到第 $r_2$ 行、第 $c_1$ 列到第 $c_2$ 列的元素。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。 对于 $a$ 的任意子矩阵，一次操作可以选择该子矩阵的一行或一列，并将一个常数（可以为负数）加到该子矩阵内的该行或该列的每个元素上。若通过一系列这样的操作，可以使某个子矩阵与 $b$ 的对应子矩阵完全相同，则称该子矩阵是可匹配的。换句话说，只有当你能为每一行 $i$ 选一个值 $h_i$，为每一列 $j$ 选一个值 $w_j$，使得对于所有 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 都有 $a_{i,j} + h_i + w_j = b_{i,j}$ 时，该子矩阵才是可匹配的。 你将被要求执行 $q$ 个操作。 操作有两种类型： - U $r_1\;c_1\;r_2\;c_2\;x$：将常数 $x$ 加到矩阵 $a$ 的子矩阵 $(r_1, c_1, r_2, c_2)$ 的所有元素上。 - Q $r_1\;c_1\;r_2\;c_2$：判断 $a$ 的子矩阵 $(r_1, c_1, r_2, c_2)$ 是否可匹配。 查询不会修改矩阵，操作仅是理论上的，每次互不影响。仅有更新操作会改变 $a$，而 $b$ 永远不会改变。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的个数。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 1000$，$1 \le q \le 2 \cdot 10^4$）——矩阵的边长和操作次数。 接下来 $n$ 行，每行 $n$ 个整数（$-10^4 \le a_{i,j} \le 10^4$），表示矩阵 $a$ 的初始状态。 接下来 $n$ 行，每行 $n$ 个整数（$-10^4 \le b_{i,j} \le 10^4$），表示矩阵 $b$。 然后是 $q$ 行操作。每行以字符 U 或 Q 开头： - U：后跟五个整数 $r_1\;c_1\;r_2\;c_2\;x$（$1 \le r_1 \le r_2 \le n$，$1 \le c_1 \le c_2 \le n$，$-10^4 \le x \le 10^4$）——将常数 $x$ 加到子矩阵 $(r_1, c_1, r_2, c_2)$ 的全部元素上。 - Q：后跟四个整数 $r_1\;c_1\;r_2\;c_2$（$1 \le r_1 \le r_2 \le n$，$1 \le c_1 \le c_2 \le n$）——查询子矩阵 $(r_1, c_1, r_2, c_2)$ 是否可匹配。 保证所有测试用例中 $n^2$ 之和不超过 $10^6$。 保证所有测试用例中 $q$ 之和不超过 $2 \cdot 10^4$。

对于每个查询，若对应的子矩阵是可匹配的，输出 "YES"（不含引号），否则输出 "NO"。 输出不区分大小写。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案。

在第一个测试用例中，更新后 $a$ 变为 $$ \begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}. $$ 对于查询，选择 $h_1=0$，$h_2=3$，$w_1=0$，$w_2=2$ 就能使子矩阵匹配，所以答案为 YES。 在第二个测试用例中，第一个查询答案为 YES：选择 $h_1=1$，$h_2=4$，$w_1=0$，$w_2=1$，$w_3=2$。第一次更新后，第二次查询时 $a$ 和 $b$ 的对应子矩阵分别为 $$ \begin{bmatrix}6 & 1 & 1 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix}, $$ 可证答案为 NO。第二次更新后，第三次查询时分别为 $$ \begin{bmatrix}6 & 6 & 6 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix}, $$ 选择 $h_1=-4$，$h_2=4$，$w_1=0$，$w_2=1$，$w_3=2$，二者匹配，答案为 YES。 在第三个测试用例中，两次更新后，第一次查询时 $a$ 和 $b$ 的对应子矩阵分别为 $$ \begin{bmatrix}1 & 0 & 0 & 0 & 0 \\ 2 & 7 & 7 & -5 & -5 \\ 3 & 7 & 7 & -5 & -5 \\ 4 & 0 & 0 & -5 & -5\end{bmatrix}, \quad \begin{bmatrix}2 & 2 & 3 & 4 & 5 \\ 4 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 6 & 7 \\ 8 & 5 & 6 & 7 & 8\end{bmatrix}, $$ 可证答案为 NO。第二次查询时分别为 $$ \begin{bmatrix}-5 & -5 \\ -5 & -5 \\ -5 & -5\end{bmatrix}, \quad \begin{bmatrix}5 & 6 \\ 6 & 7 \\ 7 & 8\end{bmatrix}, $$ 选择 $h_2=10$，$h_3=11$，$h_4=12$，$w_4=0$，$w_5=1$，二者匹配，答案为 YES。第三次查询，选 $h_2=0$，$h_3=1$，$w_1=2$，$w_2=-4$，$w_3=-3$，$w_4=10$，$w_5=11$ 也能匹配，答案为 YES。可证第四次查询答案为 NO。 由 ChatGPT 5 翻译