问题描述
2718. 查询后矩阵的和 (Medium)
给你一个整数 n 和一个下标从 0 开始的 二维数组 que ries ，其中 queries[i] = [typeᵢ, indexᵢ, valᵢ] 。
一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均
为 0 。每一个查询，你需要执行以下操作之一：
- 如果
typeᵢ == 0，将第indexᵢ行的元素全部修改为valᵢ，覆盖任何之前的值。 - 如果
typeᵢ == 1，将第indexᵢ列的元素全部修改为valᵢ，覆盖任何之前的值。
请你执行完所有查询以后，返回矩阵中所有整数的和。
示例 1：
输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩
阵元素之和为 23 。
示例 2：
输入：n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2
,1]]
输出：17
解释：上图展示了每一个查询操作之后的矩阵。所有操作执行完以后
，矩阵元素之和为 17 。
提示：
1 <= n <= 10⁴1 <= queries.length <= 5 * 10⁴queries[i].length == 30 <= typeᵢ <= 10 <= indexᵢ < n0 <= valᵢ <= 10⁵
解题思路
本题是 Leetcode 第 348 期的第三题，当时太蠢了，做了半天搞不定，一直在想是不是要用什么高级的数据结构，实际上并不难，主要是脑子要转过这个弯。
本题本质上还是个模拟题，只是如果按照题目意思，正序模拟，一步步修改数值并调整覆盖，那么就掉坑里了，必然超时。
正难则反，实际上，我们可以尝试倒序进行模拟，那么我们就不用考虑覆盖了，只需考虑行填充或者列填充时，填充多少个。
我们可以用哈希表来记录未被填充的行或者列，倒序遍历时，如果发现当前行已经被填充了，那就跳过，否则给 $total$ 加上 $val \times k$，$k$ 表示还没有被填充的列的数目；填充列的情况是类似的。
代码
class Solution {
public:
long long matrixSumQueries(int n, vector<vector<int>> &queries) {
// 倒序处理
unordered_set<int> col_hash, row_hash;
for (int i = 0; i < n; ++i) {
col_hash.insert(i);
row_hash.insert(i);
}
int m = queries.size();
long long total = 0;
for (int i = m - 1; i >= 0 && !col_hash.empty() && !row_hash.empty(); --i) {
if (queries[i][0] == 0) {
// 修改行
if (row_hash.find(queries[i][1]) == row_hash.end()) {
// 说明后面还会被修改，直接不管他
continue;
}
total += col_hash.size() * queries[i][2];
row_hash.erase(queries[i][1]);
} else {
// 修改列
if (col_hash.find(queries[i][1]) == col_hash.end()) {
continue;
}
total += row_hash.size() * queries[i][2];
col_hash.erase(queries[i][1]);
}
}
return total;
}
};