package main import ( "bufio" "fmt" "os" ) func demo() { seg := NewDynamicSegTreeSparse(0, 10, false) root := seg.NewRoot() root = seg.Set(root, 1, 1) fmt.Println(seg.Query(root, 0, 1), seg.GetAll(root)) } func main() { // https://yukicoder.me/problems/no/789 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() seg := NewDynamicSegTreeSparse(0, 1e9+10, false) root := seg.NewRoot() var n int fmt.Fscan(in, &n) res := 0 for i := 0; i < n; i++ { var op int fmt.Fscan(in, &op) if op == 0 { var a, b int fmt.Fscan(in, &a, &b) root = seg.Update(root, a, b) } else { var left, right int fmt.Fscan(in, &left, &right) res += seg.Query(root, left, right+1) } } fmt.Fprintln(out, res) } type E = int func e() E { return 0 } func op(a, b E) E { return a + b } type DynamicSegTreeSparse struct { L, R int persistent bool unit E } type SegNode struct { idx int l, r *SegNode x, prod E } func NewDynamicSegTreeSparse(left, right int, persistent bool) *DynamicSegTreeSparse { return &DynamicSegTreeSparse{ L: left, R: right, persistent: persistent, unit: e(), } } func (ds *DynamicSegTreeSparse) NewRoot() *SegNode { return nil } // L<=left<=right<=R func (ds *DynamicSegTreeSparse) Query(root *SegNode, left, right int) E { if left == right { return ds.unit } x := ds.unit ds._queryRec(root, ds.L, ds.R, left, right, &x) return x } func (ds *DynamicSegTreeSparse) QueryAll(root *SegNode) E { return ds.Query(root, ds.L, ds.R) } // L<=index> 1 if i < m { if root.idx < i { root.idx, i = i, root.idx root.x, x = x, root.x } root.l = ds._setRec(root.l, l, m, i, x) } else { if i < root.idx { root.idx, i = i, root.idx root.x, x = x, root.x } root.r = ds._setRec(root.r, m, r, i, x) } ds._pushUp(root) return root } func (ds *DynamicSegTreeSparse) _updateRec(root *SegNode, l, r, i int, x E) *SegNode { if root == nil { root = ds._newNode(i, x) return root } root = ds._copyNode(root) if root.idx == i { root.x = op(root.x, x) ds._pushUp(root) return root } m := (l + r) >> 1 if i < m { if root.idx < i { root.idx, i = i, root.idx root.x, x = x, root.x } root.l = ds._updateRec(root.l, l, m, i, x) } else { if i < root.idx { root.idx, i = i, root.idx root.x, x = x, root.x } root.r = ds._updateRec(root.r, m, r, i, x) } ds._pushUp(root) return root } func (ds *DynamicSegTreeSparse) _queryRec(root *SegNode, l, r, ql, qr int, x *E) { ql = max(ql, l) qr = min(qr, r) if ql >= qr || root == nil { return } if l == ql && r == qr { *x = op(*x, root.prod) return } m := (l + r) >> 1 ds._queryRec(root.l, l, m, ql, qr, x) if ql <= root.idx && root.idx < qr { *x = op(*x, root.x) } ds._queryRec(root.r, m, r, ql, qr, x) } func (ds *DynamicSegTreeSparse) _minLeftRec(root *SegNode, l, r, qr int, check func(E) bool, x *E) int { if root == nil || qr <= l { return ds.L } if check(op(root.prod, *x)) { *x = op(root.prod, *x) return ds.L } m := (l + r) >> 1 k := ds._minLeftRec(root.r, m, r, qr, check, x) if k != ds.L { return k } if root.idx < qr { *x = op(root.x, *x) if !check(*x) { return root.idx + 1 } } return ds._minLeftRec(root.l, l, m, qr, check, x) } func (ds *DynamicSegTreeSparse) _maxRightRec(root *SegNode, l, r, ql int, check func(E) bool, x *E) int { if root == nil || r <= ql { return ds.R } if check(op(*x, root.prod)) { *x = op(*x, root.prod) return ds.R } m := (l + r) >> 1 k := ds._maxRightRec(root.l, l, m, ql, check, x) if k != ds.R { return k } if ql <= root.idx { *x = op(*x, root.x) if !check(*x) { return root.idx } } return ds._maxRightRec(root.r, m, r, ql, check, x) } func (ds *DynamicSegTreeSparse) _getAllRec(root *SegNode, res *[]struct { index int value E }) { if root == nil { return } ds._getAllRec(root.l, res) *res = append(*res, struct { index int value E }{root.idx, root.x}) ds._getAllRec(root.r, res) } func (ds *DynamicSegTreeSparse) _getRec(root *SegNode, idx int) E { if root == nil { return ds.unit } if idx == root.idx { return root.x } if idx < root.idx { return ds._getRec(root.l, idx) } return ds._getRec(root.r, idx) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b }