#line 1 "test/yukicoder/789__dynamic_seg.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/789" #line 2 "common/util.hpp" #line 2 "common/alias.hpp" #include #include using namespace std; // using namespace std::views; // using namespace boost::multiprecision; // --- 型エイリアス --- using ll = long long; using ull = unsigned long long; template using vec = vector; template using vvec = vector>; template using vvvec = vector>>; template using p_queue = priority_queue; template using rp_queue = priority_queue, greater>; using bint = boost::multiprecision::cpp_int; // --- 黒魔術 --- #define int ll // --- 制御マクロ --- #define rep(i, n) for (ll i = 0; i < n; ++i) #define all(v) begin(v), end(v) // #define BIT(n) (1LL << (n)) #define MAX(type) numeric_limits::max() #define MIN(type) numeric_limits::min() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define pb push_back #define mp make_pair #define fir first #define sec second // --- 定数 --- constexpr ll INF = 1LL << 60; // constexpr ll INF = numeric_limits::max(); inline signed bit_width(ll x) { return bit_width((ull)x); } inline ull bit_ceil(ll x) { return bit_ceil((ull)x); } #line 2 "common/concepts.hpp" #line 4 "common/concepts.hpp" template concept addable = requires(T a, T b) { { a + b } -> convertible_to; }; #line 5 "common/util.hpp" // --- Utils --- // 二分探索 template inline T bin_search(T ok, T ng, const function is_ok) { assert(is_ok(ok)); assert(!is_ok(ng)); assert(ok < ng); while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; if (is_ok(mid)) ok = mid; else ng = mid; } return ok; } // 順列全探索 inline void rep_perm(int n, function &)> f) { vec v(n); iota(v.begin(), v.end(), 0); do { f(v); } while (next_permutation(v.begin(), v.end())); } inline void rep_bit(int n, function f) { rep(i, 1LL << n) f(i); } // 配列 to string template inline string join(const vec &v, string sep = " ") { string res = ""; rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep); return res; } template inline void join_out(ostream &os, const vec &v, string sep = " ", string end = "\n") { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? end : sep); } template inline void transform(vec &src, function f) { for (auto &val : src) f(val); } // ベース指定ceil inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; } // ベース指定floor inline ll floor(ll x, ll base) { return x / base * base; } // 合計値を求める // ll sum(const vec &v) { return accumulate(all(v), 0LL); } template T sum(const vec &v) { return accumulate(all(v), T()); } // 可変引数min template auto min(T... a) { return min(initializer_list>{a...}); } // 可変引数max template auto max(T... a) { return max(initializer_list>{a...}); } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } // 3項間不等式 // 広義単調増加 inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; } // 半開区間[x, z)にyが含まれるか? inline bool is_contained(int x, int y, int z) { return x <= y && y < z; } // 頂点(x, y)が範囲に含まれるか inline bool is_contained(int H, int W, int x, int y) { return is_contained(0, x, H) && is_contained(0, y, W); } // rootに対し、aとbが同じ側にあるか (=は含まない) inline bool is_same_side(int root, int a, int b) { return (root < a) == (root < b); } // vector継承にする? template struct vec_accumulate : public vec { explicit vec_accumulate(vec &v) : vec(v.size()) { assert(v.size() > 0); this->at(0) = v[0]; for (int i = 1; i < v.size(); ++i) this->at(i) = this->at(i - 1) + v[i]; } // [0, i]の和 // なので、-1 <= i < size() T operator[](int i) { assert(is_contained(-1, i, this->size())); if (i == -1) return T(); return this->at(i); } }; // vector func template inline void unique_erase(vec &v) { sort(all(v)); v.erase(unique(all(v)), v.end()); } void io_setup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << std::fixed << std::setprecision(15); } #line 2 "datastructure/dynamic-segment-tree.hpp" #line 4 "datastructure/dynamic-segment-tree.hpp" /** * @brief セグメント木 * * @tparam T ノードの型 */ template struct DynamicSegmentTree { private: /// 単位元 T e; /// 演算 function op; /// 要素数 int n; /// ノードの構造体 struct Node { /// ノードの値 T val; /// 初期化用の値 T e; /// 親ノード, 左の子ノード, 右の子ノード Node *p, *l_child, *r_child; /// ノードの範囲 int l, r; Node(T val, T e, int l, int r) : val(val), e(e), p(nullptr), l_child(nullptr), r_child(nullptr), l(l), r(r) {} Node(T val, Node *p, bool child_index) : val(val), e(p->e), p(p), l_child(nullptr), r_child(nullptr), l(!child_index ? p->l : p->mid()), r(!child_index ? p->mid() : p->r) {} /// ノードの範囲の中央 int mid() const { return (l + r) / 2; } /// 子ノードを取得する Node* child(bool child_index) { if(child_index == 0) { if(l_child == nullptr) l_child = new Node(e, this, 0); return l_child; } else { if(r_child == nullptr) r_child = new Node(e, this, 1); return r_child; } } /// 子ノードの情報からvalを更新する void update(auto &op) { T l_val = l_child == nullptr ? e : l_child->val; T r_val = r_child == nullptr ? e : r_child->val; val = op(l_val, r_val); } }; Node* root; public: /** * @brief 個数から空のSegmentTreeを生成する O(1) * * @param length 要素数 * @param e 単位元 * @param op 演算 */ inline explicit DynamicSegmentTree(int length, T e, function op) : e(e), op(op), n(bit_ceil(length)), root(new Node(e, e, 0, n)) {} /** * @brief i番目の要素を取得する O(log n) */ inline Node* get_node(int i) const { Node *node = root; while(node->l + 1 < node->r) { node = node->child(node->mid() <= i); } return node; } /** * @brief i番目の要素を変更する O(log n) * op * * @param i インデックス (0-indexed) * @param a 更新後の要素 */ inline void set(int i, T a) { Node *node = get_node(i); node->val = a; while(node->p != nullptr) { node = node->p; node->update(op); } } /** * @brief i番目の要素を取得する O(log n) * * @param i インデックス (0-indexed) * @return i番目の要素 */ inline T get(int i) const { return get_node(i)->val; } /** * @brief [l, r)の範囲に対するクエリを行う O(log n) * op * * @param l クエリの左端 (0-indexed) * @param r クエリの右端 (0-indexed) * @return クエリの結果 */ inline T query(int l, int r) const { return _query(root, l, r); } private: /** * @brief 特定のノードに対し、[l, r)の範囲に対するクエリを行う O(log n) * op * * @param node クエリを行うノード * @param l クエリの左端 (0-indexed) * @param r クエリの右端 (0-indexed) * @return クエリの結果 */ inline T _query(Node *node, int l, int r) const { if(r <= node->l || node->r <= l) return e; if(l <= node->l && node->r <= r) return node->val; return op(_query(node->child(0), l, r), _query(node->child(1), l, r)); } }; #line 5 "test/yukicoder/789__dynamic_seg.test.cpp" signed main() { io_setup(); int N; cin >> N; DynamicSegmentTree seg(1'000'000'001, 0, [](int a, int b) { return a + b; }); int ans = 0; rep(i, N) { int type; cin >> type; if(type == 0) { int x, y; cin >> x >> y; seg.set(x, seg.get(x) + y); } else { int l, r; cin >> l >> r; ans += seg.query(l, r + 1); } } cout << ans << endl; }