LongestIncreasingSubsequence(strictly increasing)

LIS.rb

class SegmentTree
  def initialize(n)
    @root, @nil=0, 0
    @sz=2**(Math.log(n)/Math.log(2)).ceil
    @seg=Array.new(2*@sz-1){@nil}
  end

  attr_accessor :seg

  def max(a, b, i=@root, l=0, r=@sz)
    if b<=l or r<=a
      @nil
    elsif a<=l and r<=b
      @seg[i]
    else
      m=(r+l)/2
      vl=max(a, b, 2*i+1, l, m)
      vr=max(a, b, 2*i+2, m, r)
      [vl, vr].max
    end
  end

  def update(i, data)
    i+=@sz-1
    @seg[i]=data
    while i.nonzero?
      i=(i-1)/2
      @seg[i]=[@seg[2*i+1], @seg[2*i+2]].max
    end
  end

  def answer
    @seg[@root]
  end
end

Poyo=Struct.new(:val, :id)

n=gets.to_i
a=[]
n.times do |i|
  v=gets.to_i
  a<< Poyo.new(v, i)
end

b=a.sort do |el, er|
  el.val!=er.val ? el.val<=>er.val : er.id<=>el.id
end

st=SegmentTree.new(n)
b.each do |e|
  i=e.id
  st.update(i, st.max(0, i)+1)
end

puts st.answer