This documentation is automatically generated by online-judge-tools/verification-helper

:heavy_check_mark: test/dp/inversion_test.cr

Depends on

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_5_D
require "../../src/dp/inversion"
require "../../src/collection/compress"
read_line
a = read_line.split.map(&.to_i)
puts DP.inversion(a.compress)
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_5_D
# require "../../src/dp/inversion"
# require "../datastructure/fenwick_tree"
class FenwickTree(T)
  getter size : Int32

  def initialize(size : Int)
    @size = size.to_i
    @data = Array(T).new(@size + 1, T.zero)
  end

  def initialize(array : Array(T))
    @data = [T.zero] + array
    @size = array.size
    (1...size).each do |i|
      j = i + (i & -i)
      next if j > size
      @data[j] += @data[i]
    end
  end

  # Adds *x* to *index* th element.
  def add(index : Int, x) : Nil
    raise IndexError.new unless 0 <= index < size
    index += 1
    while index <= size
      @data[index] += x
      index += index & -index
    end
  end

  # Set *x* to *index* th element.
  def set(index : Int, x) : Nil
    add(index, x - self[index])
  end

  # :ditto:
  def []=(index : Int, x) : Nil
    set(index, x)
  end

  # Culculates sum of `a[0...i]`.
  def left_sum(i : Int) : T
    raise IndexError.new unless 0 <= i <= size
    sum = T.zero
    while i > 0
      sum += @data[i]
      i -= i & -i
    end
    sum
  end

  # Returns *index* th element.
  def [](index : Int)
    left_sum(index + 1) - left_sum(index)
  end

  # Returns sum of `a[start, count]`
  def [](start : Int, count : Int) : T
    left_sum(start + count) - left_sum(start)
  end

  # Returns sum of `a[range]`
  def [](range : Range) : T
    self[*Indexable.range_to_index_and_count(range, size) || raise IndexError.new]
  end

  # Returns the elements as an Array.
  def to_a : Array(T)
    Array.new(size) { |i| self[i] }
  end
end

module DP
  extend self

  def inversion(a : Array(T)) : Int64 forall T
    bit = FenwickTree(Int32).new(a.max + 1)
    a.sum(0i64) do |x|
      bit[x + 1..].tap { bit.add(x, 1) }
    end
  end
end

# require "../../src/collection/compress"
class Array(T)
  def compress(values : Array(T), *, index : Int = 0)
    map do |x|
      index + values.bsearch_index { |y| y >= x }.not_nil!
    end
  end

  def compress(*, index : Int = 0) : Array(Int32)
    compress(uniq.sort!, index: index)
  end
end

read_line
a = read_line.split.map(&.to_i)
puts DP.inversion(a.compress)
Back to top page