提出 #33771637

---

ソースコード 拡げる

class Fenwick
  attr_accessor(:size, :node)
 
  def initialize(n)
    @size = n
    @node = Array.new(@size + 1, 0)
  end
 
  def add(p, x)
    p += 1
    while p <= @size
      @node[p] += x
      p += p & (- p)
    end
  end
 
  def sum(r)
    s = 0
    while r > 0
      s += (@node[r] || 0)
      r -= r & (- r)
    end
    return s
  end
  
  def prod(l, r)
    return sum(r) - sum(l)
  end

  def bsearch_index(x)
    if x <= 0
      return 0
    else
      res = 0
      r = 1
      while r < @size
        r <<= 1
      end
      len = r
      while len > 0
        if res + len < @size && @node[res + len] < x
          x -= @node[res + len]
          res += len
        end
        len >>= 1
      end

      return res
    end
  end
end

n, q = gets.chomp.split.map(&:to_i)
queries = []
(n - 1).times do |i|
  l, r = gets.chomp.split.map(&:to_i)
  queries << [q, l, i + 1, - 1]
  queries << [q, r + 1, i + 1, 1]
end

q.times do |i|
  a, b = gets.chomp.split.map(&:to_i)
  queries << [i, a, b, 0]
end

queries.sort_by! {|t, x, _, _| x * (q + 1) + q - t }

ft = Fenwick.new(n + 2)
(n + 2).times do |i|
  ft.add(i, 1)
end

res = Array.new(q)
queries.each do |t, _, i, d|
  if t == q
    ft.add(i, d)
  else
    c = ft.sum(i)
    lb = ft.bsearch_index(c) + 1
    ub = ft.bsearch_index(c + 1)
    res[t] = ub - lb + 1
  end
end
puts res

提出情報

ジャッジ結果