CF2273C.Matrix Puzzle

提高+/省选-

通过率:0%

时间限制:2.50s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Camila and Daniel are the greatest puzzle rivals in Mexico. For years, they have challenged each other with the hardest number games in the country, and now they have turned their attention to you. You want to prove to them that you can compete at their level, and so they present you with the following problem.

You are given two square matrices aa and bb of size n×nn \times n. The submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) of a matrix consists of the elements in rows r1r_1 to r2r_2 and columns c1c_1 to c2c_2. The rows are numbered from 11 to nn from top to bottom and the columns are numbered from 11 to nn from left to right.

In one move on a submatrix of aa, you pick one of its rows or columns and add any constant (possibly negative) to every element of that row or column inside the submatrix. The submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) of aa is matchable if some sequence of moves makes it equal to the same submatrix of bb. In other words, it is matchable if and only if you can choose a value hih_i for each row ii and a value wjw_j for each column jj such that ai,j+hi+wj=bi,ja_{i,j} + h_i + w_j = b_{i,j} for all r1≤i≤r2r_1 \le i \le r_2 and c1≤j≤c2c_1 \le j \le c_2.

You will be asked to perform qq operations.

The operations are of two types:

  • U  r1  c1  r2  c2  x\;r_1\;c_1\;r_2\;c_2\;x: Add a constant xx to every ai,ja_{i,j} in the submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2).
  • Q  r1  c1  r2  c2\;r_1\;c_1\;r_2\;c_2: Determine whether the submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) of aa is matchable.

Queries do not modify either matrix: the moves are hypothetical and are chosen independently for each query. Only update operations change aa, and bb never changes.

卡米拉和丹尼尔是墨西哥最杰出的谜题对手。多年来,他们一直以全国最难的数字游戏相互挑战,如今他们将目光转向了你。你想向他们证明自己具备与他们同台竞技的实力,因此他们向你提出了以下问题。

给你两个大小为 n×nn \times n 的方阵 aa 和 bb。矩阵的一个子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 由第 r1r_1 行至第 r2r_2 行、第 c1c_1 列至第 c2c_2 列的所有元素构成。行号从上到下依次为 11 至 nn,列号从左到右依次为 11 至 nn。

在对矩阵 aa 的某个子矩阵进行一次操作时,你可以选择该子矩阵中的一行或一列,并给该行(或该列)在该子矩阵范围内的所有元素加上任意一个常数(可以为负数)。若存在一系列操作,可使子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 上的 aa 变为与 bb 中对应位置完全相同的子矩阵,则称该子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 是可匹配的。换言之,子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 是可匹配的,当且仅当存在一组行偏移量 hih_i(对每个行号 ii)和一组列偏移量 wjw_j(对每个列号 jj),使得对所有满足 r1≤i≤r2r_1 \le i \le r_2 且 c1≤j≤c2c_1 \le j \le c_2 的 (i,j)(i,j),均有
ai,j+hi+wj=bi,j. a_{i,j} + h_i + w_j = b_{i,j}.

你将被要求执行 qq 次操作。

操作分为两类:

  • U  r1  c1  r2  c2  x\;r_1\;c_1\;r_2\;c_2\;x:将子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 内所有 ai,ja_{i,j} 均加上常数 xx;
  • Q  r1  c1  r2  c2\;r_1\;c_1\;r_2\;c_2:判断矩阵 aa 的子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 是否可匹配。

查询操作不会修改任一矩阵:每次查询所假想的操作是独立进行的;只有更新操作(U 类型)会改变 aa,而 bb 始终保持不变。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains two integers nn and qq (2≤n≤10002 \le n \le 1000, 1≤q≤2⋅1041 \le q \le 2 \cdot 10^4) — the dimension of the matrices and the number of operations.

The next nn lines of each test case contain nn integers each (−104≤ai,j≤104-10^4 \le a_{i,j} \le 10^4) — the initial state of matrix aa.

The next nn lines of each test case contain nn integers each (−104≤bi,j≤104-10^4 \le b_{i,j} \le 10^4) — the matrix bb.

Then qq lines follow for that test case. Each line starts with a character U or Q:

  • U: then five integers r1r_1, c1c_1, r2r_2, c2c_2, xx (1≤r1≤r2≤n1 \le r_1 \le r_2 \le n, 1≤c1≤c2≤n1 \le c_1 \le c_2 \le n, −104≤x≤104-10^4 \le x \le 10^4) — update the submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) by adding xx to each of its elements.
  • Q: then four integers r1r_1, c1c_1, r2r_2, c2c_2 (1≤r1≤r2≤n1 \le r_1 \le r_2 \le n, 1≤c1≤c2≤n1 \le c_1 \le c_2 \le n) — query the submatrix (r1,c1,r2,c2)(r_1, c_1, r_2, c_2).

It is guaranteed that the sum of n2n^2 over all test cases does not exceed 10610^6.

It is guaranteed that the sum of qq over all test cases does not exceed 2⋅1042 \cdot 10^4.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 qq(2≤n≤10002 \le n \le 1000,1≤q≤2⋅1041 \le q \le 2 \cdot 10^4)——分别表示矩阵的维度和操作次数。

每个测试用例的接下来 nn 行,每行包含 nn 个整数(−104≤ai,j≤104-10^4 \le a_{i,j} \le 10^4)——表示矩阵 aa 的初始状态。

每个测试用例的再接下来 nn 行,每行包含 nn 个整数(−104≤bi,j≤104-10^4 \le b_{i,j} \le 10^4)——表示矩阵 bb。

然后是该测试用例的 qq 行操作。每行以字符 U 或 Q 开头:

  • U:随后是五个整数 r1r_1, c1c_1, r2r_2, c2c_2, xx(1≤r1≤r2≤n1 \le r_1 \le r_2 \le n,1≤c1≤c2≤n1 \le c_1 \le c_2 \le n,−104≤x≤104-10^4 \le x \le 10^4)——对子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) 中的每个元素加上 xx。
  • Q:随后是四个整数 r1r_1, c1c_1, r2r_2, c2c_2(1≤r1≤r2≤n1 \le r_1 \le r_2 \le n,1≤c1≤c2≤n1 \le c_1 \le c_2 \le n)——查询子矩阵 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2)。

保证所有测试用例中 n2n^2 的总和不超过 10610^6。

保证所有测试用例中 qq 的总和不超过 2⋅1042 \cdot 10^4。

输出格式

For each query, output "YES" (without quotes) if the submatrix is matchable, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个查询,如果子矩阵是可匹配的,则输出 “YES”(不带引号),否则输出 “NO”(不带引号)。

您可以以任意大小写形式输出答案(大写或小写)。例如,字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

输入输出样例

  • 输入#1

    3
    2 2
    0 0
    0 -1
    1 2
    3 4
    U 1 1 1 1 1
    Q 1 1 2 2
    3 5
    1 1 1
    2 2 2
    3 3 3
    2 3 4
    6 7 8
    10 11 12
    Q 1 1 2 3
    U 1 1 1 1 5
    Q 1 1 2 3
    U 1 2 1 3 5
    Q 1 1 2 3
    5 6
    1 0 0 0 0
    2 0 0 0 0
    3 0 0 0 0
    4 0 0 0 0
    5 0 0 0 0
    2 2 3 4 5
    4 3 4 5 6
    6 4 5 6 7
    8 5 6 7 8
    10 6 7 8 9
    U 2 2 3 3 7
    U 2 4 4 5 -5
    Q 1 1 4 5
    Q 2 4 4 5
    Q 2 1 3 5
    Q 1 1 2 3

    输出#1

    Yes
    Yes
    No
    Yes
    No
    Yes
    Yes
    No

说明/提示

In the first test case, after the update, aa becomes [100−1].\begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}. For the query, choosing h1=0h_1=0, h2=3h_2=3, w1=0w_1=0, and w2=2w_2=2 makes the submatrices match, so the answer is YES.

In the second test case, the first query has answer YES: choose h1=1h_1=1, h2=4h_2=4, w1=0w_1=0, w2=1w_2=1, and w3=2w_3=2. After the first update, the submatrices of aa and bb in the second query are [611222],[234678],\begin{bmatrix}6 & 1 & 1 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix}, and it can be proved that the answer is NO. After the second update, in the third query they are [666222],[234678],\begin{bmatrix}6 & 6 & 6 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix}, so choosing h1=−4h_1=-4, h2=4h_2=4, w1=0w_1=0, w2=1w_2=1, and w3=2w_3=2 makes them match, and the answer is YES.

In the third test case, after both updates, the submatrices of aa and bb in the first query are [10000277−5−5377−5−5400−5−5],[22345434566456785678],\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}, and it can be proved that the answer is NO. In the second query, they are [−5−5−5−5−5−5],[566778],\begin{bmatrix}-5 & -5 \\ -5 & -5 \\ -5 & -5\end{bmatrix}, \quad \begin{bmatrix}5 & 6 \\ 6 & 7 \\ 7 & 8\end{bmatrix}, so choosing h2=10h_2=10, h3=11h_3=11, h4=12h_4=12, w4=0w_4=0, and w5=1w_5=1 makes them match, and the answer is YES. In the third query, choosing h2=0h_2=0, h3=1h_3=1, w1=2w_1=2, w2=−4w_2=-4, w3=−3w_3=-3, w4=10w_4=10, and w5=11w_5=11 makes the submatrices match, so the answer is YES. It can be proved that the answer to the fourth query is NO.

在第一个测试用例中,更新后,aa 变为 [100−1]\begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}。对于该查询,选择 h1=0h_1=0、h2=3h_2=3、w1=0w_1=0 和 w2=2w_2=2 可使两个子矩阵匹配,因此答案为 YES。

在第二个测试用例中,第一个查询的答案为 YES:选择 h1=1h_1=1、h2=4h_2=4、w1=0w_1=0、w2=1w_2=1 和 w3=2w_3=2。第一次更新后,第二个查询中 aa 与 bb 的子矩阵分别为
[611222],[234678], \begin{bmatrix}6 & 1 & 1 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix},
可证明答案为 NO。第二次更新后,第三个查询中的子矩阵为
[666222],[234678], \begin{bmatrix}6 & 6 & 6 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix},
此时选择 h1=−4h_1=-4、h2=4h_2=4、w1=0w_1=0、w2=1w_2=1 和 w3=2w_3=2 可使它们匹配,因此答案为 YES。

在第三个测试用例中,两次更新后,第一个查询中 aa 与 bb 的子矩阵分别为
[10000277−5−5377−5−5400−5−5],[22345434566456785678], \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。在第二个查询中,它们分别为
[−5−5−5−5−5−5],[566778], \begin{bmatrix}-5 & -5 \\ -5 & -5 \\ -5 & -5\end{bmatrix}, \quad \begin{bmatrix}5 & 6 \\ 6 & 7 \\ 7 & 8\end{bmatrix},
此时选择 h2=10h_2=10、h3=11h_3=11、h4=12h_4=12、w4=0w_4=0 和 w5=1w_5=1 可使它们匹配,因此答案为 YES。在第三个查询中,选择 h2=0h_2=0、h3=1h_3=1、w1=2w_1=2、w2=−4w_2=-4、w3=−3w_3=-3、w4=10w_4=10 和 w5=11w_5=11 可使子矩阵匹配,因此答案为 YES。可证明第四个查询的答案为 NO。

输入解题思路,AI测评打分。不知道怎么写?

首页