結果

問題 No.789 範囲の合計
コンテスト
ユーザー るこーそー
提出日時 2025-03-13 03:36:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 201 ms / 1,000 ms
コード長 2,190 bytes
コンパイル時間 3,565 ms
コンパイル使用メモリ 277,916 KB
実行使用メモリ 34,688 KB
最終ジャッジ日時 2025-03-13 03:36:56
合計ジャッジ時間 6,162 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 {
        S val;
        node_t *l, *r;
        node_t(S val) : val(val), l(nullptr), r(nullptr) {}
    };
    node_t *root;
    int size;

    node_t *set(node_t *x, int index, S value, int l, int r) {
        if (!x) x = new node_t(e());
        if (index < l || r <= index) return x;
        if (r - l == 1) {
            x->val = value;
            return x;
        }
        int m = (l + r) >> 1;
        if (index < m) {
            x->l = set(x->l, index, value, l, m);
        } else {
            x->r = set(x->r, index, value, m, r);
        }
        S res = e();
        if (x->l) res = op(res, x->l->val);
        if (x->r) res = op(res, x->r->val);
        x->val = res;
        return x;
    }
    S get(node_t *x, int index, int l, int r) {
        if (!x) return e();
        if (r - l == 1) return x->val;
        int m = (l + r) >> 1;
        if (index < m) {
            return get(x->l, index, l, m);
        } else {
            return get(x->r, index, m, r);
        }
    }
    S prod(node_t *x, int l, int r, int lb, int ub) {
        if (!x || ub <= l || r <= lb) return e();
        if (l <= lb && ub <= r) return x->val;
        int m = (lb + ub) >> 1;
        return op(prod(x->l, l, r, lb, m), prod(x->r, l, r, m, ub));
    }
public:
    DynamicSegTree(int n) : root(nullptr), size(1) {
        while (size < n) { size <<= 1;}
    };
    void set(int index, S value) {
        root = set(root, index, value, 0, size);
    }
    S get(int index) {
        return get(root, index, 0, size);
    }
    S prod(int l, int r) {
        return prod(root, l, r, 0, size);
    }
};

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);
    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