挺有意思的思维题
看看数据范围$1 \leq n \leq 10^4$ $1 \leq queries.length \leq 5 \times 10^4$ 就知道暴力不可行
我们发现因为覆盖操作, 后面的操作会全部或者部分地抹除之前的val
, 因此考虑倒着计算, 倒着计算的好处是一旦一个地方被填了数, 后面再遍历到这个位置就不必考虑了
维护一个已经确定了值的行数rs
和列数cs
假如现在要进行一个type = 0
的操作, 把某一行变成val
, 那么在这行已经确定了值的列的数是不能改的, 因此只能再确定n - cs
个数, 同时这一操作使得这一行变为了修改完毕
type = 1
同理
倒序计算即可
class Solution {
public:
using ll = long long;
long long matrixSumQueries(int n, vector<vector<int>>& q) {
vector<bool> row(n), col(n);
int rs = 0, cs = 0;
ll res = 0;
for (int i = q.size() - 1; i >= 0; i --) {
int type = q[i][0], idx = q[i][1], val = q[i][2];
if (type == 0) {
if (row[idx]) continue;
row[idx] = true;
res += (ll)(n - cs) * val;
rs += 1;
}
else {
if (col[idx]) continue;
col[idx] = true;
res += (ll)(n - rs) * val;
cs += 1;
}
}
return res;
}
};
retyrn的题解写得真不错。不知道为啥力扣周赛为什么这么喜欢出思维题。感觉面试的时候思维题出得都不是很多