void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } void main () { import std; // yukicoder No.789 範囲の合計 long len = 10^^9; auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len); int N = readln.chomp.to!int; // seg.dump(); // writeln(); long ans = 0; foreach (i; 0..N) { int t, l, r; readln.read(t, l, r); if (t == 0) { seg.set(l, seg.get(l) + r); } if (t == 1) { ans += seg.prod(l, r + 1); } } writeln(ans); } import std.traits : ReturnType, isCallable, Parameters; import std.meta : AliasSeq; class DynamicSegmentTree (T, alias ope, alias e) { // TODO: assertのメッセージを表示 static assert(isCallable!(ope)); static assert(isCallable!(e)); static assert(is (ReturnType!(ope) == T)); static assert(is (ReturnType!(e) == T)); static assert(is (Parameters!(ope) == AliasSeq!(T, T))); static assert(is (Parameters!(e) == AliasSeq!())); // 内部が1-indexedで動的な完全二分セグメント木 import std.format : format; public: this (long N_) in { assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18)); } do { length = N_; // N_以上の2冪に設定 if ((N_ & (-N_)) == N_) { N = N_; } else { // msb+1 bitを立てる foreach_reverse (i; 0..63) { if (0 < (N_ & (1L << i))) { N = 1L << (i + 1); break; } } } root = new node(1, N + 1, e(), null, null); } void set (long idx, T val) { idx++; internal_set(root, idx, idx + 1, val, 1, N + 1); } T get (long idx) { idx++; return internal_prod(root, idx, idx + 1); } T prod (long l, long r) { // 1-indexed l++, r++; return internal_prod(root, l, r); } void dump () { void dfs (const node *cur) { if (cur == null) { return; } import std.stdio : writefln; writefln("range: [%s %s), value: %s", cur.left, cur.right, cur.value); dfs(cur.left_child); dfs(cur.right_child); } dfs(root); } private: struct node { long left, right; T value; node *left_child = null, right_child = null; } node *root; long N = 0; long length = 0; // [l, r) : 今いる場所の本来あるべき区間 void internal_set (ref node *cur, long a, long b, T v, long l, long r) { // 途中までで切り上げる if (cur == null) { cur = new node(a, b, v, null, null); return; } if (a == l && b == r) { cur.value = v; return; } // 途中で打ち切られたノードを発見 if (cur.left != l || cur.right != r) { T vv = cur.value; long ll = cur.left, rr = cur.right; // 区間修正 -> 先にあったノードを直す cur.left = l; cur.right = r; internal_set(cur, ll, rr, vv, l, r); } // 下に潜る long mid = (l + r) / 2; if (b <= mid) { internal_set(cur.left_child, a, b, v, l, mid); } else { internal_set(cur.right_child, a, b, v, mid, r); } // 自分の値を更新 cur.value = ope( (cur.left_child == null ? e() : cur.left_child.value), (cur.right_child == null ? e() : cur.right_child.value)); } T internal_prod (const node *cur, long a, long b) { // まだ作られていない = その区間は初期値 if (cur == null) return e(); long l = cur.left, r = cur.right; if (b <= l || r <= a) return e(); // 包含 if (a <= l && r <= b) return cur.value; // 部分包含は必要部分を縮めて渡す import std.algorithm : min, max; a = max(a, l); b = min(b, r); long mid = (l + r) / 2; if (b <= mid) return internal_prod(cur.left_child, a, b); if (mid <= a) return internal_prod(cur.right_child, a, b); return ope( internal_prod(cur.left_child, a, mid), internal_prod(cur.right_child, mid, b) ); } }