結果

問題 No.789 範囲の合計
ユーザー RyoichRyoich
提出日時 2022-12-28 02:29:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 87 ms / 1,000 ms
コード長 4,727 bytes
コンパイル時間 2,455 ms
コンパイル使用メモリ 209,492 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-11-22 15:31:53
合計ジャッジ時間 4,161 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 86 ms
6,016 KB
testcase_03 AC 63 ms
5,248 KB
testcase_04 AC 87 ms
6,144 KB
testcase_05 AC 72 ms
5,888 KB
testcase_06 AC 74 ms
5,888 KB
testcase_07 AC 51 ms
5,248 KB
testcase_08 AC 72 ms
6,656 KB
testcase_09 AC 68 ms
6,272 KB
testcase_10 AC 80 ms
5,248 KB
testcase_11 AC 57 ms
6,272 KB
testcase_12 AC 55 ms
6,272 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// clang-format off
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define drep(i, n) for (ll i = ll(n - 1); i >= 0; i--)
#define rng(a) (a).begin(), (a).end()
#define rrng(a) (a).rbegin(), (a).rend()
#define sz(x) (ll)(x).size()
#define cto const auto&
#define popcount __builtin_popcount
#ifdef _DEBUG
#include <debug_print.hpp>
#define deb(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define deb(...) (static_cast<void>(0))
#endif
template<class T> inline bool chmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; }
template<class T> inline bool chmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; }
template<class T> inline void print_vec(const vector<T>& x) { rep(i, sz(x)) cout << x[i] << " \n"[i+1==sz(x)]; }
template<class T> inline void uniq_vec(vector<T>& x) { sort(rng(x)); x.erase(unique(rng(x)), x.end()); }
inline void FASTER_IO() { cin.tie(0)->sync_with_stdio(false); cout << fixed << setprecision(20); }
// clang-format on

using ld = long double;
using P = pair<int, int>;
constexpr char el = '\n';
constexpr int INF = 1001001001;
constexpr ll LINF = 2e18;
constexpr int mod = 1000000007;

// 1. A set S equipped with a binary operation S × S → S
// 2. Associativity
// 3. Identity element
template <class Monoid> class DynamicSegmentTree {
    using F = function<Monoid(Monoid, Monoid)>;

    struct Node;
    using Node_ptr = unique_ptr<Node>;
    struct Node {
        size_t idx;
        Monoid val, product;
        Node_ptr left, right;
        Node(size_t idx, Monoid val) : idx(idx), val(val), product(val), left(nullptr), right(nullptr) {}

        void update(const DynamicSegmentTree& x) {
            const auto& combine = x.combine;
            const auto& id = x.identity;
            product = combine(left ? left->product : id, right ? right->product : id);
            product = combine(product, val);
        }
    };

    const size_t n;
    Node_ptr root;
    F combine;
    Monoid identity;

    void set(Node_ptr& t, size_t l, size_t r, size_t i, Monoid val) const {
        if (!t) {
            t = make_unique<Node>(i, val);
            return;
        }
        if (t->idx == i) {
            t->val = val;
            t->update(*this);
            return;
        }
        size_t mid = (l + r) >> 1;
        if (i < mid) {
            if (t->idx < i) swap(t->idx, i), swap(t->val, val);
            set(t->left, l, mid, i, val);
        } else {
            if (t->idx > i) swap(t->idx, i), swap(t->val, val);
            set(t->right, mid, r, i, val);
        }
        t->update(*this);
    }

    Monoid get(const Node_ptr& t, size_t l, size_t r, size_t i) const {
        if (!t) return identity;
        if (t->idx == i) return t->val;
        size_t mid = (l + r) >> 1;
        return i < mid ? get(t->left, l, mid, i) : get(t->right, mid, r, i);
    }

    Monoid fold(const Node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return identity;
        if (l <= a && b <= r) return t->product;
        size_t c = (a + b) >> 1;
        Monoid res = fold(t->left, a, c, l, r);
        if (l <= t->idx && t->idx < r) res = combine(res, t->val);
        return combine(res, fold(t->right, c, b, l, r));
    }

    void reset(Node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return;
        if (l <= a && b <= r) {
            t.reset();
            return;
        }
        size_t c = (a + b) >> 1;
        reset(t->left, a, c, l, r);
        reset(t->right, c, b, l, r);
        t->update(*this);
    }

public:
    DynamicSegmentTree(size_t n, const F& combine, Monoid identity)
        : n(n), combine(combine), identity(identity), root(nullptr) {}

    // set a[i] = val
    void set(size_t i, Monoid val) { set(root, 0, n, i, val); }

    // return value in a[i]
    Monoid get(size_t i) const { return get(root, 0, n, i); }

    // return combine[l, r)
    Monoid fold(size_t l, size_t r) const { return fold(root, 0, n, l, r); }

    Monoid all_fold() const { return root ? root->product : identity; }

    void reet(size_t l, size_t r) { reset(root, 0, n, l, r); }
};

int main() {
    FASTER_IO();

    DynamicSegmentTree<ll> seg(
        1e10, [](ll x, ll y) { return x + y; }, 0ll);

    int q;
    cin >> q;
    ll ans = 0;
    while (q--) {
        int type;
        cin >> type;
        if (type == 0) {
            int i;
            ll val;
            cin >> i >> val;
            seg.set(i, seg.get(i) + val);
        } else {
            int l, r;
            cin >> l >> r;
            ans += seg.fold(l, r + 1);
        }
    }
    cout << ans << el;

    return 0;
}
0