結果

問題 No.789 範囲の合計
コンテスト
ユーザー だれ
提出日時 2023-11-17 17:53:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 144 ms / 1,000 ms
コード長 2,565 bytes
コンパイル時間 903 ms
コンパイル使用メモリ 78,388 KB
最終ジャッジ日時 2025-02-17 22:21:41
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <new>
#include <utility>
#include <vector>

template <class T, T op(T, T), T e()>
struct DynamicSegTree {
    using i64 = long long;

    struct node {
        node *left, *right;
        T prod;
        T val;
        i64 pos;
        node(int p, T x)
            : left(nullptr), right(nullptr), prod(x), val(x), pos(p) {}

        void update() {
            prod = op(op((left ? left->prod : e()), val),
                      (right ? right->prod : e()));
        }
    };

    node* root;
    i64 n;
    DynamicSegTree(i64 _n) : n(_n), root(nullptr) {}

    void _set(node*& t, i64 p, T& x, i64 l, i64 r) {
        if (!t) {
            t = new node(p, x);
            return;
        }
        if (t->pos == p) {
            t->val = x;
        } else {
            i64 mid = (l + r) >> 1;
            if (p < mid) {
                if (t->pos < p) {
                    std::swap(t->pos, p);
                    std::swap(t->val, x);
                }
                _set(t->left, p, x, l, mid);
            } else {
                if (t->pos > p) {
                    std::swap(t->pos, p);
                    std::swap(t->val, x);
                }
                _set(t->right, p, x, mid, r);
            }
        }
        t->update();
        return;
    }

    T _get(node*& t, i64 p, i64 l, i64 r) {
        if (!t) return e();
        if (t->pos == p) return t->val;
        i64 mid = (l + r) >> 1;
        if (p < mid)
            return _get(t->left, p, l, mid);
        else
            return _get(t->right, p, mid, r);
    }

    T _prod(node*& t, i64 L, i64 R, i64 l, i64 r) {
        if (!t || R <= l || r <= L) return e();
        if (L <= l && r <= R) return t->prod;
        i64 mid = (l + r) >> 1;
        T res = _prod(t->left, L, R, l, mid);
        if (L <= t->pos && t->pos < R) res = op(res, t->val);
        return op(res, _prod(t->right, L, R, mid, r));
    }

    void set(i64 p, T x) { _set(root, p, x, 0, n); }

    T get(i64 p) { return _get(root, p, 0, n); }

    T prod(i64 l, i64 r) { return _prod(root, l, r, 0, n); }
};

using namespace std;

using i64 = long long;

i64 op(i64 a, i64 b) { return a + b; }

i64 e() { return 0; }

int main() {
    int q;
    cin >> q;
    DynamicSegTree<i64, op, e> seg(1e9 + 1000);
    i64 ans = 0;
    while (q--) {
        int t;
        i64 l, r;
        cin >> t >> l >> r;
        if (t == 0)
            seg.set(l, seg.get(l) + r);
        else {
            ans += seg.prod(l, r + 1);
        }
    }
    cout << ans << "\n";
}
0