結果

問題 No.789 範囲の合計
コンテスト
ユーザー AC2K
提出日時 2023-05-04 13:14:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 292 ms / 1,000 ms
コード長 3,034 bytes
コンパイル時間 939 ms
コンパイル使用メモリ 92,992 KB
実行使用メモリ 50,560 KB
最終ジャッジ日時 2024-11-22 06:28:18
合計ジャッジ時間 4,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#line 2 "main.cpp"
#include <cassert>
#include <memory>
namespace kyopro {
/// @brief 動的セグメント木
template <class S, S (*op)(S, S), S (*e)()>
class dynamic_segtree {
public:
    dynamic_segtree(size_t n = 0) : n(n), root(nullptr) { root = new Node(); }
    ~dynamic_segtree() { delete root; }

private:
    struct Node {
        S val;
        Node *l, *r, *parent;

        Node(const S& v = e(), Node* pt = nullptr)
            : val(v), l(nullptr), r(nullptr), parent(pt){}
        ~Node() { delete l, delete r; }
    };
    using ptr = Node*;

    Node* root;
    size_t n;

private:
    Node* find(size_t i) {
        assert(0 <= i && i < n);

        size_t l = 0, r = n;

        Node* p = root;
        
        while (r - l > 1) {
            size_t md = (r + l) >> 1;
            if (i < md) {
                if (!p->l) {
                    p->l = new Node(e(), p);
                }
                p = p->l;
                r = md;
            } else {
                if (!p->r) {
                    p->r = new Node(e(), p);
                }
                p = p->r;
                l = md;
            }
        }
        return p;
    }
    void push(Node* p) {
        while (p = p->parent) {
            p->val = op((p->l ? p->l->val : e()), (p->r ? p->r->val : e()));
        }
    }

public:
    void apply(size_t i, const S& x) {
        assert(0 <= i && i < n);
        auto p = find(i);
        p->val = op(p->val, x);
        push(p);
    }
    void update(size_t i, const S& x) {
        assert(0 <= i && i < n);
        auto p = find(i);
        p->val = x;
        push(p);
    }
    S at(size_t i) {
        assert(0 <= i && i < n);
        return find(i)->val;
    }
    S prod(size_t l, size_t r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) {
            return e();
        }
        return internal_prod(root, 0, n, l, r);
    }

private:
    //TODO:非再帰にする
    S internal_prod(const Node* p, size_t l, size_t r, size_t L, size_t R) const {
        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
#include <iostream>
constexpr inline int op(int x, int y) { return x + y; }
constexpr 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.apply(x, y);
        } else {
            size_t l, r;
            std::cin >> l >> r;
            ans += seg.prod(l, r + 1);
        }
    }
    std::cout << ans << '\n';
}
0