結果

問題 No.789 範囲の合計
コンテスト
ユーザー るこーそー
提出日時 2025-03-14 09:55:13
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 146 ms / 1,000 ms
コード長 2,241 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,788 ms
コンパイル使用メモリ 281,012 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-14 09:55:20
合計ジャッジ時間 6,317 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

template <typename M> // Mは 型type, 単位元id(), 演算op() を持つモノイド
class dynamic_segment_tree {
    using T = typename M::type;
    struct node {
        int pos;
        T val, all;
        node *l, *r;
        node(int p, T v)
            : pos(p), val(v), all(v), l(nullptr), r(nullptr) {}
    };
private:
    const int n;
    node *root;
public:
    dynamic_segment_tree(int n_) :
        n(1 << (int)ceil(log2(n_))), root(nullptr) {}
    void update(int p, T val) {
        root = change(root, p, val, 0, n);
    }
    T find(int l, int r) {
        return get(l, r, root, 0, n);
    }
private:
    T value(node *t) {
        return t ? t->all : M::id();
    }
    T get(int l, int r, node* t, int lb, int ub) {
        if (!t || ub <= l || r <= lb) return M::id();
        if (l <= lb && ub <= r) return t->all;
        int c = (lb + ub) / 2;
        T res = get(l, r, t->l, lb, c);
        if (l <= t->pos && t->pos < r) res = M::op(res, t->val);
        return M::op(res, get(l, r, t->r, c, ub));
    }
    node *change(node* t, int p, T val, int lb, int ub) {
        if (!t) return new node(p, val);
        if (t->pos == p) {
            t->val = val;
            t->all = M::op(value(t->l), M::op(t->val, value(t->r)));
            return t;
        }
        int c = (lb + ub) / 2;
        if (p < c) {
            if (p > t->pos) swap(p, t->pos), swap(val, t->val);
            t->l = change(t->l, p, val, lb, c);
        }
        else {
            if (p < t->pos) swap(p, t->pos), swap(val, t->val);
            t->r = change(t->r, p, val, c, ub);
        }
        t->all = M::op(value(t->l), M::op(t->val, value(t->r)));
        return t;
    }
};

int main() {
    int n;
    cin >> n;

    struct M {
        using type=int;
        static type id() {return 0;}
        static type op(type a, type b) {return a+b;}
    };
    dynamic_segment_tree<M> dst(1e9+1);
    long long ans=0;
    while (n--) {
        int q,x,y,l,r;
        cin >> q;
        if (q==0){
            cin >> x >> y;
            dst.update(x, dst.find(x,x+1)+y);
        }else {
            cin >> l >> r;
            ans+=dst.find(l,r+1);
        }
    }
    cout << ans << endl;
}
0