2718. 查询后矩阵的和

题目描述：

给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ，其中 queries[i] = [typei, indexi, vali] 。

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

如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值。

如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值。

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

示例 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 。

解题思路：

这道题很巧妙，所以我决定把它分享出来。

这道题正常来讲，读完题第一反应就是直接暴力就能做，就改数呗，然后加和呗。

但是这有点太暴力了，那就优化一下，不改所有的数了，就改每一行的和和每一列的和呗，最后再统计一下总和。但这样似乎好像也不是很好实现。因为我们把每一行和每一列的和记录下来之后，最后算总和的时候是不太好计算的，因为后改变的会覆盖先改变的，所以我们还得知道行和列改变的顺序关系才行。

那考虑到这，注意到加粗的“顺序关系”了么，没错，这就是解题关键。

后改变的会覆盖先改变的，也就是说，我只需要从最后改变的开始往前遍历就行了，最后改变的一定是贡献给最终答案的，那先前改变的就没有作用了。所以无论是行还是列，我们都只关注他是不是最后改变的，我们从后往前遍历的话，也就是关注他是不是第一个出现的，如果是那就更新最终的答案的值，如果不是说明在这个操作后面有另一个操作把它覆盖了，这个操作不起作用。

代码：

class Solution {
public:
    long long matrixSumQueries(int n, vector& queries) {
        long long int ans = 0;
        unordered_set vis[2]; //0表示行是否被修改，1表示列是否被修改
        int m = queries.size();
        for(int i = m - 1 ; i >= 0 ; i--){
            auto &q = queries[i];
            int type = q[0] , index = q[1] , val = q[2];
            if(!vis[type].count(index)){//如果该行/列没有被修改过
                ans += (long long int)(n-vis[type^1].size())*val;//更新答案，该行/列首次发生改变的数要加到最终答案里
                vis[type].insert(index);//标记该行/列已经被修改过
            }
        }
        return ans;
    }
};