可以发现,前面修改的行会被后面修改的行覆盖,前面修改的列会被后面修改的列覆盖,因此倒序枚举操作。
-
倒序枚举,当该行或该列已经被访问时,直接跳过
-
若修改行,则加上$(n - cnt) * val$,由于该行中有$cnt$ 个已经确定的单元格,只能修改未被确定的行的单元格,列同理
-
时间复杂度$O(m)$
class Solution {
public:
long long matrixSumQueries(int n, vector<vector<int>>& q) {
int m = q.size();
set<int> row, col;
int cnt_row = 0, cnt_col = 0; //分别存行的个数和列的个数
long long res = 0;
for(int i = m - 1;i >= 0;i --){ //倒序枚举
int a = q[i][0], b = q[i][1], c = q[i][2];
if(!a){
if(row.count(b)) continue; //已遍历过
res += (n - cnt_col) * c; //需要减去已经确定的列的个数
cnt_row ++;
}
else{
if(col.count(b)) continue; //已遍历过
res += (n - cnt_row) * c; //需要减去已经确定的行的个数
cnt_col ++;
}
if(a == 0) row.insert(b);
if(a == 1) col.insert(b);
}
return res;
}
};