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 a and b of size n×n. The submatrix (r1,c1,r2,c2) of a matrix consists of the elements in rows r1 to r2 and columns c1 to c2. The rows are numbered from 1 to n from top to bottom and the columns are numbered from 1 to n from left to right.
In one move on a submatrix of a, 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) of a is matchable if some sequence of moves makes it equal to the same submatrix of b. In other words, it is matchable if and only if you can choose a value hi for each row i and a value wj for each column j such that ai,j+hi+wj=bi,j for all r1≤i≤r2 and c1≤j≤c2.
You will be asked to perform q operations.
The operations are of two types:
- Ur1c1r2c2x: Add a constant x to every ai,j in the submatrix (r1,c1,r2,c2).
- Qr1c1r2c2: Determine whether the submatrix (r1,c1,r2,c2) of a is matchable.
Queries do not modify either matrix: the moves are hypothetical and are chosen independently for each query. Only update operations change a, and b never changes.
卡米拉和丹尼尔是墨西哥最杰出的谜题对手。多年来,他们一直以全国最难的数字游戏相互挑战,如今他们将目光转向了你。你想向他们证明自己具备与他们同台竞技的实力,因此他们向你提出了以下问题。
给你两个大小为 n×n 的方阵 a 和 b。矩阵的一个子矩阵 (r1,c1,r2,c2) 由第 r1 行至第 r2 行、第 c1 列至第 c2 列的所有元素构成。行号从上到下依次为 1 至 n,列号从左到右依次为 1 至 n。
在对矩阵 a 的某个子矩阵进行一次操作时,你可以选择该子矩阵中的一行或一列,并给该行(或该列)在该子矩阵范围内的所有元素加上任意一个常数(可以为负数)。若存在一系列操作,可使子矩阵 (r1,c1,r2,c2) 上的 a 变为与 b 中对应位置完全相同的子矩阵,则称该子矩阵 (r1,c1,r2,c2) 是可匹配的。换言之,子矩阵 (r1,c1,r2,c2) 是可匹配的,当且仅当存在一组行偏移量 hi(对每个行号 i)和一组列偏移量 wj(对每个列号 j),使得对所有满足 r1≤i≤r2 且 c1≤j≤c2 的 (i,j),均有
ai,j+hi+wj=bi,j.
你将被要求执行 q 次操作。
操作分为两类:
- Ur1c1r2c2x:将子矩阵 (r1,c1,r2,c2) 内所有 ai,j 均加上常数 x;
- Qr1c1r2c2:判断矩阵 a 的子矩阵 (r1,c1,r2,c2) 是否可匹配。
查询操作不会修改任一矩阵:每次查询所假想的操作是独立进行的;只有更新操作(U 类型)会改变 a,而 b 始终保持不变。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and q (2≤n≤1000, 1≤q≤2⋅104) — the dimension of the matrices and the number of operations.
The next n lines of each test case contain n integers each (−104≤ai,j≤104) — the initial state of matrix a.
The next n lines of each test case contain n integers each (−104≤bi,j≤104) — the matrix b.
Then q lines follow for that test case. Each line starts with a character U or Q:
- U: then five integers r1, c1, r2, c2, x (1≤r1≤r2≤n, 1≤c1≤c2≤n, −104≤x≤104) — update the submatrix (r1,c1,r2,c2) by adding x to each of its elements.
- Q: then four integers r1, c1, r2, c2 (1≤r1≤r2≤n, 1≤c1≤c2≤n) — query the submatrix (r1,c1,r2,c2).
It is guaranteed that the sum of n2 over all test cases does not exceed 106.
It is guaranteed that the sum of q over all test cases does not exceed 2⋅104.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 q(2≤n≤1000,1≤q≤2⋅104)——分别表示矩阵的维度和操作次数。
每个测试用例的接下来 n 行,每行包含 n 个整数(−104≤ai,j≤104)——表示矩阵 a 的初始状态。
每个测试用例的再接下来 n 行,每行包含 n 个整数(−104≤bi,j≤104)——表示矩阵 b。
然后是该测试用例的 q 行操作。每行以字符 U 或 Q 开头:
- U:随后是五个整数 r1, c1, r2, c2, x(1≤r1≤r2≤n,1≤c1≤c2≤n,−104≤x≤104)——对子矩阵 (r1,c1,r2,c2) 中的每个元素加上 x。
- Q:随后是四个整数 r1, c1, r2, c2(1≤r1≤r2≤n,1≤c1≤c2≤n)——查询子矩阵 (r1,c1,r2,c2)。
保证所有测试用例中 n2 的总和不超过 106。
保证所有测试用例中 q 的总和不超过 2⋅104。
输出格式
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, a becomes [100−1]. For the query, choosing h1=0, h2=3, w1=0, and w2=2 makes the submatrices match, so the answer is YES.
In the second test case, the first query has answer YES: choose h1=1, h2=4, w1=0, w2=1, and w3=2. After the first update, the submatrices of a and b in the second query are [621212],[263748], and it can be proved that the answer is NO. After the second update, in the third query they are [626262],[263748], so choosing h1=−4, h2=4, w1=0, w2=1, and w3=2 makes them match, and the answer is YES.
In the third test case, after both updates, the submatrices of a and b in the first query are 1234077007700−5−5−50−5−5−5,24682345345645675678, and it can be proved that the answer is NO. In the second query, they are −5−5−5−5−5−5,567678, so choosing h2=10, h3=11, h4=12, w4=0, and w5=1 makes them match, and the answer is YES. In the third query, choosing h2=0, h3=1, w1=2, w2=−4, w3=−3, w4=10, and w5=11 makes the submatrices match, so the answer is YES. It can be proved that the answer to the fourth query is NO.
在第一个测试用例中,更新后,a 变为 [100−1]。对于该查询,选择 h1=0、h2=3、w1=0 和 w2=2 可使两个子矩阵匹配,因此答案为 YES。
在第二个测试用例中,第一个查询的答案为 YES:选择 h1=1、h2=4、w1=0、w2=1 和 w3=2。第一次更新后,第二个查询中 a 与 b 的子矩阵分别为
[621212],[263748],
可证明答案为 NO。第二次更新后,第三个查询中的子矩阵为
[626262],[263748],
此时选择 h1=−4、h2=4、w1=0、w2=1 和 w3=2 可使它们匹配,因此答案为 YES。
在第三个测试用例中,两次更新后,第一个查询中 a 与 b 的子矩阵分别为
1234077007700−5−5−50−5−5−5,24682345345645675678,
可证明答案为 NO。在第二个查询中,它们分别为
−5−5−5−5−5−5,567678,
此时选择 h2=10、h3=11、h4=12、w4=0 和 w5=1 可使它们匹配,因此答案为 YES。在第三个查询中,选择 h2=0、h3=1、w1=2、w2=−4、w3=−3、w4=10 和 w5=11 可使子矩阵匹配,因此答案为 YES。可证明第四个查询的答案为 NO。
输入解题思路,AI测评打分。不知道怎么写?