NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

比赛链接：

https://atcoder.jp/contests/abc253

F - Operations on a Matrix

题意：

\(n * m\) 的初始值全为 0 的矩阵，\(q\) 次询问，有三种操作。
操作 1：l 到 \(r\) 所有列的所有元素都加上 \(x\)。
操作 2：将第 \(i\) 列所有元素都替换成 \(x\)。
操作 3：查询 \((i, j)\) 的元素值。

思路：

行列分开来考虑，对于列，可以通过树状数组维护一个差分数组去计算。
对于行，对这个位置有影响的只有最近的一次操作 2，每次将最近的一次操作 2 记录下来，然后查询的时候进行修改。
查询的位置的答案就是改行最近一次操作 2 的赋值 + 在这次操作之后所有对该位置有影响的操作 1 的值。
\(ans_{i,j} = r + s_j - s_r\)
\(ans_{i,j}\) 就是最后的答案。
\(r\) 是查询的这一行最近的一次操作 2。
\(s_j\) 表示到当前这一步所有操作的第 \(i\) 列的值。
\(s_r\) 表示到查询的这一行最近的一次操作 2 的所有操作的第 \(i\) 列的值。
可以考虑每一个操作 2 对后面查询值的影响，在读入时记录下每个操作 2 的影响，然后再通过一个树状数组去求最终的答案。
即先求出 \(r + s_j\) 然后再逐个减去 \(s_r\)。

代码：

#include 
using namespace std;
#define LL long long
struct fwt{
	LL n;
	vector  a;
	fwt(LL n) : n(n), a(n + 1) {}
	LL sum(LL x){
		LL res = 0;
		for (; x; x -= x & -x)
			res += a[x];
		return res;
	}
	void add(LL x, LL k){
		for (; x <= n; x += x & -x)
			a[x] += k;
	}
	LL query(LL x, LL y){
		return sum(y) - sum(x - 1);
	}
};
LL n, m, q;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m >> q;
	vector  op(q), l(q), r(q), x(q), ans(q);
	vector < vector < pair < LL, LL> > > sub(q);
	vector < pair < LL, LL> > last(n + 1);
	fwt f(m);
	for (int i = 0; i < q; i ++ ){
		cin >> op[i];
		if (op[i] == 1){
			cin >> l[i] >> r[i] >> x[i];
			f.add(l[i], x[i]);
			f.add(r[i] + 1, -x[i]);
		}
		else if (op[i] == 2){
			cin >> r[i] >> x[i];
			last[r[i]] = {i, x[i]};
		}
		else{
			cin >> l[i] >> r[i];
			auto [p, num] = last[l[i]];
			ans[i] = num + f.sum(r[i]);
			sub[p].push_back({i, r[i]});
		}
	}
	fwt t(m);
	for (int i = 0; i < q; i ++ ){
		for (auto [p, c] : sub[i])
			ans[p] -= t.sum(c);
		if (op[i] == 1){
			t.add(l[i], x[i]);
			t.add(r[i] + 1, -x[i]);
		}
		if (op[i] == 3)
			cout << ans[i] << "\n";
	}
	return 0;
}