#1157225 (C++23) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: ruthen71
• 提出日時: 2026-04-13 19:11:51
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 170 ms / 1,000 ms
• コード長: 5,175 bytes
• コンパイル時間: 1,275 ms
• コンパイル使用メモリ: 167,580 KB
• 実行使用メモリ: 50,816 KB
• 最終ジャッジ日時: 2026-04-13 19:11:59
• 合計ジャッジ時間: 4,446 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
other	AC * 15

ソースコード

// #define PROBLEM "https://yukicoder.me/problems/no/789"
// 
// #include <iostream>
// 
// #include "../../algebra/monoid/monoid_plus.hpp"
// #include "../../segment_tree/dynamic_segment_tree.hpp"
// 
// int main() {
//     int n;
//     std::cin >> n;
//     const int m = 1000000001;
//     // Q log_2(N) = n log_2(m) = 3000000 くらい
//     DynamicSegmentTree<MonoidPlus<long long>, 3000000> seg_add(m);
//     DynamicSegmentTree<MonoidPlus<long long>, 3000000> seg_set(m);
//     long long ans = 0;
//     for (int i = 0; i < n; i++) {
//         int type;
//         std::cin >> type;
//         if (type == 0) {
//             int x, y;
//             std::cin >> x >> y;
//             seg_add.add(x, y);
//             seg_set.set(x, seg_set.get(x) + y);
//         } else {
//             int l, r;
//             std::cin >> l >> r;
//             r++;
//             assert(seg_add.prod(l, r) == seg_set.prod(l, r));
//             ans += seg_add.prod(l, r);
//         }
//     }
//     std::cout << ans << '\n';
//     return 0;
// }
#define PROBLEM "https://yukicoder.me/problems/no/789"

#include <iostream>

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};

#include <cassert>
#include <vector>

// Dynamic Segment Tree
// Q log_2(N) は Q = 500000, N = 10^18 のとき 30000000 くらい
template <class MS, int MAX_NODES = 30'000'000> struct DynamicSegmentTree {
  public:
    using S = typename MS::value_type;

    struct Node {
        S d;
        Node *l, *r;
        Node() = default;
        Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {}
    };

    DynamicSegmentTree() = default;

    explicit DynamicSegmentTree(int n) : n(n), root(nullptr) {}

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        set(p, x, 0, n, root);
    }

    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, x, 0, n, root);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S get(int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, n, root);
    }

    S all_prod() const { return root->d; }

  private:
    int n;
    Node* root;
    static inline Node pool[MAX_NODES];
    static inline int pool_idx = 0;

    Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) {
        return &(pool[pool_idx++] = Node(v, l, r));
    }

    Node* merge(Node* l, Node* r, Node* np) {
        S ld = (l == nullptr ? MS::identity() : l->d);
        S rd = (r == nullptr ? MS::identity() : r->d);
        np->d = MS::operation(ld, rd);
        return np;
    }

    Node* set(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = x;
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(set(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, set(p, x, m, r, np->r), np);
        }
    }

    Node* add(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = MS::operation(np->d, x);
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(add(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, add(p, x, m, r, np->r), np);
        }
    }

    S prod(int ql, int qr, int l, int r, Node* np) const {
        if (np == nullptr) return MS::identity();
        //  [ql, qr) と [l, r) が交差しない
        if (qr <= l or r <= ql) return MS::identity();
        // [ql, qr) が [l, r) を完全に含んでいる
        if (ql <= l and r <= qr) return np->d;
        int m = (l + r) / 2;
        return MS::operation(prod(ql, qr, l, m, np->l),
                             prod(ql, qr, m, r, np->r));
    }
};

int main() {
    int n;
    std::cin >> n;
    const int m = 1000000001;
    // Q log_2(N) = n log_2(m) = 3000000 くらい
    DynamicSegmentTree<MonoidPlus<long long>, 3000000> seg_add(m);
    DynamicSegmentTree<MonoidPlus<long long>, 3000000> seg_set(m);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int type;
        std::cin >> type;
        if (type == 0) {
            int x, y;
            std::cin >> x >> y;
            seg_add.add(x, y);
            seg_set.set(x, seg_set.get(x) + y);
        } else {
            int l, r;
            std::cin >> l >> r;
            r++;
            assert(seg_add.prod(l, r) == seg_set.prod(l, r));
            ans += seg_add.prod(l, r);
        }
    }
    std::cout << ans << '\n';
    return 0;
}