class AcLibraryRb::LazySegtree
Segment tree with Lazy propagation
Attributes
composition[RW]
d[R]
e[R]
id[R]
lz[R]
mapping[RW]
op[RW]
Public Class Methods
new(v, a1, a2, a3 = nil, a4 = nil, a5 = nil, &op_block)
click to toggle source
new(v, op, e, mapping, composition, id) new(v, e, id, op, mapping, composition) new(v, e, id){ |x, y| }
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 10 def initialize(v, a1, a2, a3 = nil, a4 = nil, a5 = nil, &op_block) if a1.is_a?(Proc) @op, @e, @mapping, @composition, @id = a1, a2, a3, a4, a5 else @e, @id, @op, @mapping, @composition = a1, a2, a3, a4, a5 @op ||= op_block end v = Array.new(v, @e) if v.is_a?(Integer) @n = v.size @log = (@n - 1).bit_length @size = 1 << @log @d = Array.new(2 * @size, e) @lz = Array.new(@size, id) @n.times { |i| @d[@size + i] = v[i] } (@size - 1).downto(1) { |i| update(i) } end
Public Instance Methods
all_apply(k, f)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 211 def all_apply(k, f) @d[k] = @mapping.call(f, @d[k]) @lz[k] = @composition.call(f, @lz[k]) if k < @size end
all_prod()
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 93 def all_prod @d[1] end
apply(pos, f, fr = nil)
click to toggle source
apply(pos, f) apply(l, r, f) -> range_apply
(l, r, f) apply(l…r, f) -> range_apply
(l, r, f) … [Experimental]
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 100 def apply(pos, f, fr = nil) if fr return range_apply(pos, f, fr) elsif pos.is_a?(Range) l = pos.begin l += @n if l < 0 if r = pos.end r += @n if r < 0 r += 1 unless pos.exclude_end? else r = @n end return range_apply(l, r, f) end pos += @size @log.downto(1) { |i| push(pos >> i) } @d[pos] = @mapping.call(f, @d[pos]) 1.upto(@log) { |i| update(pos >> i) } end
get(pos)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 46 def get(pos) pos += @size @log.downto(1) { |i| push(pos >> i) } @d[pos] end
Also aliased as: []
max_right(l, &g)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 149 def max_right(l, &g) return @n if l == @n l += @size @log.downto(1) { |i| push(l >> i) } sm = @e loop do while l.even? l >>= 1 end unless g.call(@op.call(sm, @d[l])) while l < @size push(l) l <<= 1 if g.call(@op.call(sm, @d[l])) sm = @op.call(sm, @d[l]) l += 1 end end return l - @size end sm = @op.call(sm, @d[l]) l += 1 break if l & -l == l end @n end
min_left(r, &g)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 178 def min_left(r, &g) return 0 if r == 0 r += @size @log.downto(1) { |i| push((r - 1) >> i) } sm = @e loop do r -= 1 while r > 1 && r.odd? r /= 2 end unless g.call(@op.call(@d[r], sm)) while r < @size push(r) r = r * 2 + 1 if g.call(@op.call(@d[r], sm)) sm = @op.call(@d[r], sm) r -= 1 end end return r + 1 - @size end sm = @op.call(@d[r], sm) break if (r & -r) == r end 0 end
prod(l, r = nil)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 53 def prod(l, r = nil) if r.nil? # if 1st argument l is Range if r = l.end r += @n if r < 0 r += 1 unless l.exclude_end? else r = @n end l = l.begin l += @n if l < 0 end return @e if l == r l += @size r += @size @log.downto(1) do |i| push(l >> i) if (l >> i) << i != l push(r >> i) if (r >> i) << i != r end sml = @e smr = @e while l < r if l.odd? sml = @op.call(sml, @d[l]) l += 1 end if r.odd? r -= 1 smr = @op.call(@d[r], smr) end l >>= 1 r >>= 1 end @op.call(sml, smr) end
push(k)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 216 def push(k) all_apply(2 * k, @lz[k]) all_apply(2 * k + 1, @lz[k]) @lz[k] = @id end
range_apply(l, r, f)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 121 def range_apply(l, r, f) return if l == r l += @size r += @size @log.downto(1) do |i| push(l >> i) if (l >> i) << i != l push((r - 1) >> i) if (r >> i) << i != r end l2 = l r2 = r while l < r (all_apply(l, f); l += 1) if l.odd? (r -= 1; all_apply(r, f)) if r.odd? l >>= 1 r >>= 1 end l = l2 r = r2 1.upto(@log) do |i| update(l >> i) if (l >> i) << i != l update((r - 1) >> i) if (r >> i) << i != r end end
set(pos, x)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 38 def set(pos, x) pos += @size @log.downto(1) { |i| push(pos >> i) } @d[pos] = x 1.upto(@log) { |i| update(pos >> i) } end
Also aliased as: []=
set_composition(&composition)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 34 def set_composition(&composition) @composition = composition end
set_mapping(&mapping)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 30 def set_mapping(&mapping) @mapping = mapping end
update(k)
click to toggle source
# File lib_lock/ac-library-rb/lazy_segtree.rb, line 207 def update(k) @d[k] = @op.call(@d[2 * k], @d[2 * k + 1]) end