sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G" #include <bits/stdc++.h> #include "../../data-structure/range_fenwick_tree.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; RangeFenwickTree<long long> ft(n + 1); for (int i = 0; i < q; i++) { int type, s, t; cin >> type >> s >> t; --s; --t; if (type == 0) { int x; cin >> x; ft.add(s, t + 1, x); } else { cout << ft.prefix_sum(t + 1) - ft.prefix_sum(s) << "\n"; } } }
#line 1 "test/aoj/DSL_2_G.range_fenwick_tree.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G" #include <bits/stdc++.h> #line 3 "data-structure/range_fenwick_tree.hpp" template <typename T> class RangeFenwickTree { public: RangeFenwickTree() = default; explicit RangeFenwickTree(int n) : n(n), data0(n + 1), data1(n + 1) {} T prefix_sum(int i) const { return prefix_sum(data0, i) * (i - 1) + prefix_sum(data1, i); } void add(int l, int r, T x) { add(data0, l, x); add(data0, r, -x); add(data1, l, -x * (l - 1)); add(data1, r, x * (r - 1)); } private: int n; std::vector<T> data0, data1; T prefix_sum(const std::vector<T>& data, int i) const { T ret = 0; for (; i > 0; i -= i & -i) ret += data[i]; return ret; } void add(std::vector<T>& data, int i, T x) { for (++i; i <= n; i += i & -i) data[i] += x; } }; #line 7 "test/aoj/DSL_2_G.range_fenwick_tree.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; RangeFenwickTree<long long> ft(n + 1); for (int i = 0; i < q; i++) { int type, s, t; cin >> type >> s >> t; --s; --t; if (type == 0) { int x; cin >> x; ft.add(s, t + 1, x); } else { cout << ft.prefix_sum(t + 1) - ft.prefix_sum(s) << "\n"; } } }