问题描述 链接到标题

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 == 3
  • 0 <= typeᵢ <= 1
  • 0 <= indexᵢ < n
  • 0 <= 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;
    }
};