結果

問題 No.789 範囲の合計
コンテスト
ユーザー AC2K
提出日時 2023-05-04 12:24:43
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 294 ms / 1,000 ms
コード長 2,739 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,420 ms
コンパイル使用メモリ 251,696 KB
実行使用メモリ 82,176 KB
最終ジャッジ日時 2024-11-22 05:46:26
合計ジャッジ時間 7,208 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 2 "main.cpp"
#include<bits/stdc++.h>
#line 5 "main.cpp"
namespace kyopro {
/// @brief 動的セグメント木
template <class S, S (*op)(S, S), S (*e)()>
class dynamic_segtree {
public:
    dynamic_segtree(size_t n) : n(n), root(nullptr) {}

private:
    struct Node {
        S val;
        std::shared_ptr<Node> l, r;
        std::shared_ptr<Node> parent;
        Node(const S& v, std::shared_ptr<Node> parent)
            : val(v), l(nullptr), r(nullptr), parent(parent) {}
    };
    using sptr = std::shared_ptr<Node>;

    sptr root = nullptr;
    size_t n;
    S fold(const sptr& p) const { return p ? p->val : e(); }

public:
    void update(size_t i, const S& v) {
        if (!root) {
            root = std::make_shared<Node>(e(), nullptr);
        }
        size_t ng = 0, ok = n;

        sptr ptr = root;
        while (ok - ng > 1) {
            size_t md = (ng + ok) >> 1;
            if (i < md) {
                if (!(ptr->l)) {
                    ptr->l = std::make_shared<Node>(e(), ptr);
                }
                ptr = ptr->l;
                ok = md;
            } else {
                if (!(ptr->r)) {
                    ptr->r = std::make_shared<Node>(e(), ptr);
                }
                ptr = ptr->r;
                ng = md;
            }
        }
        ptr->val = v;
        while (ptr->parent) {
            ptr->parent->val = op(fold(ptr->parent->l), fold(ptr->parent->r));
            ptr = ptr->parent;
        }
    }
    S prod(size_t l, size_t r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) {
            return e();
        }
        return internal_prod(root, 0, n, l, r);
    }

private:
    S internal_prod(sptr& p, size_t l, size_t r, size_t L, size_t R) {
        if (!p || r <= L || R <= l) {
            return e();
        }
        if (L <= l && r <= R) {
            return p->val;
        }

        size_t mid = (l + r) >> 1;
        return op(internal_prod(p->l, l, mid, L, R),
                  internal_prod(p->r, mid, r, L, R));
    }
};
};  // namespace kyopro

/// @docs docs/data-structure/dynamic_segtree.md
#line 82 "main.cpp"
inline int op(int x, int y) { return x + y; }
inline int e() { return 0; }
int main() {
    const size_t n = 1000000001;
    kyopro::dynamic_segtree<int, op, e> seg(n);

    int q;
    std::cin >> q;
    long long ans = 0;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 0) {
            size_t x;
            long long y;
            std::cin >> x >> y;
            seg.update(x, seg.prod(x, x + 1) + y);
        } else {
            size_t l, r;
            std::cin >> l >> r;
            ans += seg.prod(l, r + 1);
        }
    }
    std::cout << ans << '\n';
}
0