package main import ( "bufio" "fmt" "io" "math" "os" "strconv" ) // 解答欄 func solve(in *input, out, outErr *output) { n := in.nextInt() sg := NewSegmentTree(0, 1e9+1, func() int { return 0 }, func(a, b int) int { return a + b }) ans := 0 for i := 0; i < n; i++ { switch q := in.nextInt(); q { case 0: x, y := in.nextInt2() tmp := sg.Get(x) sg.Set(x, tmp+y) case 1: l, r := in.nextInt2() r++ tmp := sg.Product(l, r) ans += tmp } } out.println(ans) } // ポインタを使う 必要な部分だけ作るやつ type SegmentTree[T any] struct { l, r int root *node[T] e func() T op func(a, b T) T } func NewSegmentTree[T any](l, r int, e func() T, op func(a, b T) T) *SegmentTree[T] { return &SegmentTree[T]{ l: l, r: r, root: nil, e: e, op: op, } } func (sg *SegmentTree[T]) Set(i int, val T) { sg.checkInRange(i) if sg.root == nil { sg.root = newNode(i, val) return } p := (*node[T])(nil) now := sg.root for l, r := sg.l, sg.r; ; { if m := (l + r) / 2; i < m { if i > now.i { i, now.i = now.i, i val, now.val = now.val, val } p, now = now, now.l r = m } else { if i < now.i { i, now.i = now.i, i val, now.val = now.val, val } p, now = now, now.r l = m } if i == p.i { p.val = val break } else if now == nil { now = newNode(i, val) now.p = p if now.i < p.i { p.l = now } else { p.r = now } break } } // iが存在した場合: now以下は変更してないので更新不要 // iが存在しなかった場合: nowは葉なので更新不要 // よってp以上のノードを更新する for upd := p; upd != nil; upd = upd.p { sg.update(upd) } } func (sg *SegmentTree[T]) Get(i int) T { sg.checkInRange(i) if n, _ := sg.search(i); n != nil && n.i == i { return n.val } return sg.e() } func (sg *SegmentTree[T]) Product(l, r int) T { sg.checkInRange(l) sg.checkInRange(r - 1) if sg.root == nil { return sg.e() } return sg.product(sg.root, l, r, sg.l, sg.r) } func (sg *SegmentTree[T]) product(n *node[T], argL, argR, l, r int) T { if n == nil || r <= argL || argR <= l { return sg.e() } if argL <= l && r <= argR { return n.subVal } m := (l + r) / 2 res := sg.product(n.l, argL, argR, l, m) if argL <= n.i && n.i < argR { res = sg.op(res, n.val) } res = sg.op(res, sg.product(n.r, argL, argR, m, r)) return res } func (sg *SegmentTree[T]) ProductAll() T { return sg.root.subVal } func (sg *SegmentTree[T]) update(n *node[T]) { n.subVal = sg.op(sg.subtreeVal(n.l), n.val) n.subVal = sg.op(n.subVal, sg.subtreeVal(n.r)) } // インデックスがiに近いノードとそのノードの深さを返す // ノードの個数が0の時、深さは-1になる func (sg *SegmentTree[T]) search(i int) (*node[T], int) { p := (*node[T])(nil) depth := 0 for now := sg.root; now != nil; { p = now if i == now.i { return now, depth } else if i < now.i { now = now.l } else { now = now.r } depth++ } return p, depth - 1 } func (sg *SegmentTree[T]) subtreeVal(n *node[T]) T { if n != nil { return n.subVal } return sg.e() } func (sg *SegmentTree[T]) checkInRange(i int) { if i < sg.l || sg.r <= i { panic(fmt.Sprintf("SegmentTree: index out of range: l=%d, r=%d, i=%d", sg.l, sg.r, i)) } } type node[T any] struct { i int val, subVal T p, l, r *node[T] } func newNode[T any](i int, val T) *node[T] { return &node[T]{ i: i, val: val, subVal: val, } } // 入出力の準備(in, out, outErr) func main() { const ( // インタラクティブ問題の時 true // バッファ無し出力に変更する。入力は変わらない interactiveProblem = false // 「X個のテストケースが与えられる」系の問題の時 true // 入力の一番最初でテストケース数が与えられる場合のみ使える variableSolveCount = false ) const startBufSize = 4096 const maxBufSize = math.MaxInt64 in := &input{sc: bufio.NewScanner(os.Stdin)} in.sc.Buffer(make([]byte, startBufSize), maxBufSize) in.sc.Split(bufio.ScanWords) out := &output{} if interactiveProblem { out.w = os.Stdout } else { bw := bufio.NewWriter(os.Stdout) out.w = bw defer func() { if err := bw.Flush(); err != nil { panic(fmt.Errorf("flush error: %w", err)) } }() } outErr := &output{w: os.Stderr} loop := 1 if variableSolveCount { if _, err := fmt.Scan(&loop); err != nil { panic(fmt.Errorf("valiableSolveCount = %v, loop = %v: %w", variableSolveCount, loop, err)) } } for i := 0; i < loop; i++ { solve(in, out, outErr) } } type input struct{ sc *bufio.Scanner } func (in *input) nextString() string { in.sc.Scan() return in.sc.Text() } func (in *input) nextStrings(n int) []string { res := make([]string, n) for i := range res { res[i] = in.nextString() } return res } func (in *input) nextRunes() []rune { return []rune(in.nextString()) } func (in *input) nextInt() int { s := in.nextString() res, err := strconv.Atoi(s) if err != nil { panic(fmt.Errorf("in.nextInt: %w", err)) } return res } func (in *input) nextInts(n int) []int { res := make([]int, n) for i := range res { res[i] = in.nextInt() } return res } func (in *input) nextFloat() float64 { s := in.nextString() res, err := strconv.ParseFloat(s, 64) if err != nil { panic(fmt.Errorf("in.nextFloat: %w", err)) } return res } func (in *input) nextFloats(n int) []float64 { res := make([]float64, n) for i := range res { res[i] = in.nextFloat() } return res } func (in *input) nextInt2() (int, int) { return in.nextInt(), in.nextInt() } func (in *input) nextInt3() (int, int, int) { return in.nextInt(), in.nextInt(), in.nextInt() } func (in *input) nextInt4() (int, int, int, int) { return in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt() } type output struct{ w io.Writer } func (out *output) print(a ...any) { if _, err := fmt.Fprint(out.w, a...); err != nil { panic(fmt.Errorf("out.print: %w", err)) } } func (out *output) printf(format string, a ...any) { out.print(fmt.Sprintf(format, a...)) } func (out *output) println(a ...any) { out.print(fmt.Sprintln(a...)) } // simple math functions for int func max(as ...int) int { res := as[0] for _, a := range as { if res < a { res = a } } return res } func min(as ...int) int { res := as[0] for _, a := range as { if res > a { res = a } } return res } func chMax(a *int, b int) { *a = max(*a, b) } func chMin(a *int, b int) { *a = min(*a, b) } func abs(a int) int { if a < 0 { return -a } return a } func pow(a, n int) int { res := 1 b := a for n > 0 { if n&1 > 0 { res *= b } n >>= 1 b *= b } return res } func sum(s ...int) int { res := 0 for _, v := range s { res += v } return res } // slice utility functions func fillSlice[T any](s []T, v T) { for i := range s { s[i] = v } } func countSlice[T comparable](s []T, v T) int { res := 0 for _, w := range s { if w == v { res++ } } return res }