# 2718. 查询后矩阵的和 (Medium)

## 问题描述
[2718. 查询后矩阵的和 (Medium)](https://leetcode.cn/problems/sum-of-matrix-after-queries/)
给你一个整数 `n` 和一个下标从 **0** 开始的 **二维数组** `que
ries` ，其中 `queries[i] = [typeᵢ, indexᵢ, valᵢ]` 。

一开始，给你一个下标从 **0** 开始的 `n x n` 矩阵，所有元素均
为 `0` 。每一个查询，你需要执行以下操作之一：

- 如果 `typeᵢ == 0` ，将第 `indexᵢ` 行的元素全部修改为 `valᵢ
` ，覆盖任何之前的值。
- 如果 `typeᵢ == 1` ，将第 `indexᵢ` 列的元素全部修改为 `valᵢ
` ，覆盖任何之前的值。

请你执行完所有查询以后，返回矩阵中所有整数的和。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065421.png)

```
输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩
阵元素之和为 23 。

```

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065424.png)

```
输入：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$ 表示还没有被填充的列的数目；填充列的情况是类似的。

## 代码
```cpp
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;
    }
};
```