Submission #57098548

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BIT
  attr_accessor(:arr, :size)
  def initialize(n)
    @size = n
    @arr = Array.new(@size+1,0)
  end
  def add(i,x)
    while i <= @size
      @arr[i] += x
      i += i & -i
    end
  end
  def sum(i)
    sum = 0
    while i > 0
      sum += @arr[i]
      i &= i - 1
    end
    sum
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class BIT
  attr_accessor(:arr, :size)
  def initialize(n)
    @size = n
    @arr = Array.new(@size+1,0)
  end

  def add(i,x)
    while i <= @size
      @arr[i] += x
      i += i & -i
    end
  end

  def sum(i)
    sum = 0
    while i > 0
      sum += @arr[i]
      i &= i - 1
    end
    sum
  end

  def lower_bound(x) #「bitがx個立っているところ」を指す！bsearchの代わりに
    return -1 if x <= 0
    ret = -1
    k = 1
    k <<= 1 while 2*k <= @size
    while k > 0
        if ret+k < @size && @arr[ret+k+1] < x
            x -= @arr[ret+k+1]
            ret += k
        end
        k >>= 1
    end
    ret + 2
  end

end

n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)

bit_a = BIT.new(n+1)
bit_b = BIT.new(n+1)
n.times do |i|
  bit_a.add(i+1,a[i])
  bit_b.add(i+1,1) if b[i] >= 2
end

q = gets.to_i
memo = {}
q.times do
  query = gets.split.map(&:to_i)
  if query[0] == 1
    i,x = query[1..]
    bit_a.add(i,x-a[i-1])
    a[i-1] = x
    memo = {}
  elsif query[0] == 2
    i,x = query[1..]
    if b[i-1] == 1 && x != 1
      bit_b.add(i,1)
    elsif b[i-1] != 1 && x == 1
      bit_b.add(i,-1)
    end
    b[i-1] = x
    memo = {}
  else
    l,r = query[1..]
    if memo[[l,r]]
      puts memo[[l,r]]
    else
      sum = 0
      left = l
      right = r+1
      while left < right
        if sum+a[left-1] < sum*b[left-1]
          sum *= b[left-1]
        else
          sum += a[left-1]
        end
        left_bit_count = bit_b.sum(left)
        next_left = bit_b.lower_bound(left_bit_count+1)
        next_left = right if next_left >= right
        sum += bit_a.sum(next_left-1) - bit_a.sum(left)
        left = next_left
      end
      memo[[l,r]] = sum
      puts sum
    end
  end
end

Submission Info

Judge Result