阅读量:2
题目描述：
给你一个整数 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<vector<int>>& queries) { long long int ans = 0; unordered_set<int> 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; } }; 