1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <bits/stdc++.h> #include <fenwick_tree_2d> template <class T> class fenwick_range_sum { using fenwick_2d = fenwick_sum_2d<T>; fenwick_2d t, ti, tj, tij; void add_(int i, int j, T x) { t.add(i, j, x); ti.add(i, j, x * i); tj.add(i, j, x * j); tij.add(i, j, x * i * j); } T prefix_sum_(int i, int j) const { int u = i + 1, v = j + 1; return t.prefix_sum(i, j) * u * v - ti.prefix_sum(i, j) * v - tj.prefix_sum(i, j) * u + tij.prefix_sum(i, j); }
public: fenwick_range_sum() : fenwick_range_sum(0, 0) {} explicit fenwick_range_sum(int n, int m) : t(n, m), ti(n, m), tj(n, m), tij(n, m) {} fenwick_range_sum(fenwick_range_sum const&) = default; fenwick_range_sum(fenwick_range_sum&&) = default; fenwick_range_sum& operator=(fenwick_range_sum const&) = default; fenwick_range_sum& operator=(fenwick_range_sum&&) = default;
void add(int il, int jl, int ir, int jr, T x) { auto [n, m] = t.size(); assert(0 <= il && il <= ir && ir <= n && 0 <= jl && jl <= jr && jr <= m); add_(il, jl, x); if (ir < n) add_(ir, jl, -x); if (jr < m) add_(il, jr, -x); if (ir < n && jr < m) add_(ir, jr, x); } T sum(int il, int jl, int ir, int jr) const { auto [n, m] = t.size(); assert(0 <= il && il <= ir && ir <= n && 0 <= jl && jl <= jr && jr <= m); --il, --jl, --ir, --jr; return prefix_sum_(ir, jr) - prefix_sum_(il, jr) - prefix_sum_(ir, jl) + prefix_sum_(il, jl); } std::pair<int, int> size() const { return t.size(); } }; using namespace std; using ll = long long; using fenwick_2d = fenwick_range_sum<ll>; int main() { ios::sync_with_stdio(false), cin.tie(0); int N, M, op, il, jl, ir, jr; ll x; cin >> N >> M; fenwick_2d fw(N, M); while (cin >> op >> il >> jl >> ir >> jr) { --il, --jl; if (op == 1) { cin >> x; fw.add(il, jl, ir, jr, x); } else { cout << fw.sum(il, jl, ir, jr) << '\n'; } } }
|