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

• 問題: No.789 範囲の合計
• ユーザー: champignon
• 提出日時: 2026-04-22 22:26:20
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 83 ms / 1,000 ms
• コード長: 3,280 bytes
• コンパイル時間: 2,862 ms
• コンパイル使用メモリ: 338,252 KB
• 実行使用メモリ: 34,944 KB
• 最終ジャッジ日時: 2026-04-22 22:26:45
• 合計ジャッジ時間: 4,948 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include<bits/stdc++.h>

using namespace std;

#define rep(i, l, n) for(int i = int(l); i < int(n); ++i)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template<class T> bool chmin(T &a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T &a, T b) {if(a < b) {a = b; return true;} return false;}
template<class T> using spq = priority_queue<T, vector<T>, greater<T>>;

// bool -> Yes/No
string answer(bool b) {return b ? "Yes" : "No";}

void fix(int k) {cout << fixed << setprecision(k);}

const int inf = 1000000009;
const long long INF = 2000000000000000009;
const long double eps = 1e-12;
const long double pi = acos(-1);
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

template<class S, S(*op)(S, S), S(*e)()>
struct Dynamic_Segment_Tree {
    
private:
    long long N;
    S unit = e();

    struct Node {

        S val;
        Node *lch, *rch;

        Node() : val(e()), lch(nullptr), rch(nullptr) {}
        Node(S v) : val(v), lch(nullptr), rch(nullptr) {}
        void update() {
            val = op(!lch ? e() : lch->val, !rch ? e() : rch->val);
        }

    };

    Node *root = new Node();

    void _set(Node *&x, long long pos, S v, long long l, long long r) {
        if(l + 1 == r) {
            x->val = v;
            return;
        }
        long long m = (l + r) >> 1;
        if(pos < m) {
            if(!x->lch) x->lch = new Node();
            _set(x->lch, pos, v, l, m);
        }
        else {
            if(!x->rch) x->rch = new Node();
            _set(x->rch, pos, v, m, r);
        }
        x->update();
    }

    S _prod(Node *&x, long long ql, long long qr, long long l, long long r) {
        if(ql == l && qr == r) return x->val;
        long long m = (l + r) >> 1;
        S ret = unit;
        if(ql < m && x->lch) ret = op(_prod(x->lch, ql, std::min(qr, m), l, m), ret);
        if(m < qr && x->rch) ret = op(ret, _prod(x->rch, std::max(ql, m), qr, m, r));
        return ret;
    }

public:
    Dynamic_Segment_Tree() {}
    Dynamic_Segment_Tree(long long n) : N(n) {}
    void set(long long pos, S v) {_set(root, pos, v, 0, N);}
    S get(long long pos) {
        long long l = 0, r = N;
        Node *t = root;
        while(l + 1 < r) {
            long long m = (l + r) >> 1;
            if(pos < m) {
                if(!t->lch) return unit;
                t = t->lch, r = m;
            }
            else {
                if(!t->rch) return unit;
                t = t->rch, l = m;
            }
        }
        return t->val;
    }
    S prod(long long l, long long r) {return _prod(root, l, r, 0, N);}

};

using S = long;
S op(S a, S b) {return a + b;}
S e() {return 0l;}

void main_program() {
    int Q; cin >> Q;
    Dynamic_Segment_Tree<S, op, e> seg(inf);
    long ans = 0;
    while(Q--) {
        int t; cin >> t;
        if(t) {
            int l, r; cin >> l >> r;
            ans += seg.prod(l, ++r);
        }
        else {
            int pos; long v; cin >> pos >> v;
            seg.set(pos, seg.get(pos) + v);
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while(T--) main_program();
}