题目描述
给你一个整数 n
和一个下标从 0 开始的 二维数组 queries
,其中 queries[i] = [type_i, index_i, val_i]
。
一开始,给你一个下标从 0 开始的 n x n
矩阵,所有元素均为 0
。每一个查询,你需要执行以下操作之一:
- 如果
type_i == 0
,将第index_i
行的元素全部修改为val_i
,覆盖任何之前的值。 - 如果
type_i == 1
,将第index_i
列的元素全部修改为val_i
,覆盖任何之前的值。
请你执行完所有查询以后,返回矩阵中所有整数的和。
样例
输入:n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出:23
解释:上图展示了每个查询以后矩阵的值。所有操作执行完以后,矩阵元素之和为 23。
输入:n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
输出:17
解释:上图展示了每一个查询操作之后的矩阵。所有操作执行完以后,矩阵元素之和为 17。
限制
1 <= n <= 10^4
1 <= queries.length <= 5 * 10^4
queries[i].length == 3
0 <= type_i <= 1
0 <= index_i < n
0 <= val_i <= 10^5
算法
(思维题) $O(n + q)$
- 逆序处理操作,并记录每一行和每一列的是否被处理,已经当前剩余没有被处理的行和列的个数。
- 对于每一个行的操作,如果当前行没有处理过,则答案累加剩余列的个数乘 $val$,然后标记当前行已处理。
- 对于每一个列的操作同理。
时间复杂度
- 预处理需要 $O(n)$ 的时间。
- 仅需要常数的时间处理每个操作。
- 故总时间复杂度为 $O(n + q)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储行列是否处理过。
C++ 代码
#define LL long long
class Solution {
public:
LL matrixSumQueries(int n, vector<vector<int>>& queries) {
vector<bool> r(n, false), c(n, false);
int nr = n, nc = n;
LL ans = 0;
for (int i = queries.size() - 1; i >= 0; i--) {
if (queries[i][0] == 0 && !r[queries[i][1]]) {
ans += (LL)(queries[i][2]) * nc;
r[queries[i][1]] = true;
--nr;
} else if (queries[i][0] == 1 && !c[queries[i][1]]) {
ans += (LL)(queries[i][2]) * nr;
c[queries[i][1]] = true;
--nc;
}
}
return ans;
}
};