結果

問題 No.789 範囲の合計
コンテスト
ユーザー るこーそー
提出日時 2025-03-13 08:42:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 295 ms / 1,000 ms
コード長 2,374 bytes
コンパイル時間 3,788 ms
コンパイル使用メモリ 283,592 KB
実行使用メモリ 34,944 KB
最終ジャッジ日時 2025-03-13 08:42:43
合計ジャッジ時間 6,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <class S, S (*op)(S, S), S (*e)()>
class DynamicSegTree {
private:
    struct node_t;
    using u64 = uint64_t;
    using node_ptr = unique_ptr<node_t>;
    struct node_t {
        S val;
        node_ptr l, r;
        node_t(S val) : val(val), l(nullptr), r(nullptr) {}
    };
    node_ptr root;
    u64 size;

    void set(node_ptr& x, u64 index, S value, u64 l, u64 r) {
        if (!x) x = make_unique<node_t>(e());
        if (index < l || r <= index) return;
        if (r - l == 1) {
            x->val = value;
            return;
        }
        u64 m = l + ((r - l) >> 1);
        if (index < m) {
            set(x->l, index, value, l, m);
        } else {
            set(x->r, index, value, m, r);
        }
        x->val = e();
        if (x->l) x->val = op(x->val, x->l->val);
        if (x->r) x->val = op(x->val, x->r->val);
    }
    S get(node_ptr& x, u64 index, u64 l, u64 r) {
        if (!x) return e();
        if (r - l == 1) return x->val;
        u64 m = l + ((r - l) >> 1);
        if (index < m) {
            return get(x->l, index, l, m);
        } else {
            return get(x->r, index, m, r);
        }
    }
    S prod(node_ptr& x, u64 l, u64 r, u64 lb, u64 ub) {
        if (!x || ub <= l || r <= lb) return e();
        if (l <= lb && ub <= r) return x->val;
        u64 mb = lb + ((ub - lb) >> 1);
        return op(prod(x->l, l, r, lb, mb), prod(x->r, l, r, mb, ub));
    }
public:
    DynamicSegTree(u64 n) : root(nullptr), size(n) {}
    void set(u64 index, S value) {
        assert (0 <= index && index < size);
        set(root, index, value, (u64)0, size);
    }
    S get(u64 index) {
        assert (0 <= index && index < size);
        return get(root, index, (u64)0, size);
    }
    S prod(u64 l, u64 r) {
        return prod(root, l, r, (u64)0, size);
    }
    S all_prod() {
        return root ? root->val : e();
    }
};

using S=int;
S op(auto x,auto y){return x+y;}
S e(){return 0;}
    
int main() {
    int n;
    cin >> n;
    DynamicSegTree<S,op,e> dst(1e9+1);
    long long ans=0;
    for (int i=0;i<n;i++){
        int q,x,y,l,r;
        cin >> q;
        if (q==0){
            cin >> x >> y;
            dst.set(x,dst.get(x)+y);
        }else {
            cin >> l >> r;
            ans+=dst.prod(l,r+1);
        }
    }
    cout << ans << endl;
}
0