一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

F - Operations on a Matrix

---

二、解题报告

1、思路分析

我们通过差分树状数组，可以轻松解决操作1

操作3我们也可以通过树状数组来获取对应列的值

关键是操作2会对操作3造成影响

所以我们先对询问离线处理，记录每个操作2影响到的操作3

然后顺序处理操作

当遇到操作2，我们将其影响的操作3（i, j）设置初值为 ans = x - col[j]，（col[j] 为 第j列累加的值）

遇到操作3时 输出ans + col[j]

2、复杂度

时间复杂度： O(qlogm)空间复杂度：O(Q + N + M)

3、代码详解

 ​

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1E-9;template<typename T>
class FenWick {
private:int n;std::vector<T> tr;
public:FenWick(int _n) : n(_n), tr(_n + 1) {}FenWick(const std::vector<T> &_init) : FenWick(_init.size()) {init(_init);}void init(const std::vector<T> &_init) {for (int i = 1; i <= n; ++ i) {tr[i] += _init[i - 1];int j = i + (i & -i);if (j <= n)tr[j] += tr[i];}}void add(T x, T k) {for (; x <= n; x += x & -x) tr[x] += k;}void add(T l, T r, T k) {add(l, k), add(r + 1, -k);}T query(T x) const {T res = T{};for (; x; x &= x - 1) res += tr[x];return res;}T query(T l, T r) const {if (l > r) return T{};return query(r) - query(l - 1);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + tr[x + i] <= k) {x += i;cur = cur + tr[x];}}return x;}
};struct query{int op, a, b, c;
};void solve() {int n, m, q;std::cin >> n >> m >> q;std::vector<query> Q(q);std::vector<std::vector<int>> val(q);std::vector<int> last(n, -1);for (int i = 0; i < q; ++ i) {std::cin >> Q[i].op >> Q[i].a >> Q[i].b;if (Q[i].op == 1)std::cin >> Q[i].c;else if(Q[i].op == 2)last[Q[i].a - 1] = i;else if(~last[Q[i].a - 1])val[last[Q[i].a - 1]].push_back(i);}    std::vector<i64> ans(q);FenWick<i64> tr(m + 1);for (int i = 0; i < q; ++ i) {if (Q[i].op == 1) {tr.add(Q[i].a, Q[i].c);tr.add(Q[i].b + 1, -Q[i].c);}else if(Q[i].op == 2) {for (int j : val[i])ans[j] = Q[i].b - tr.query(Q[j].b);}else {std::cout << ans[i] + tr.query(Q[i].b) << '\n';}}
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}