結果

問題 No.3464 Max and Sum on Grid
コンテスト
ユーザー tomerun
提出日時 2026-02-28 15:57:08
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 7,235 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,625 ms
コンパイル使用メモリ 344,232 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-28 15:57:41
合計ジャッジ時間 22,158 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Mo
  include Enumerable(Tuple(Int32, Int32, Int32))

  def initialize(@n : Int32, @bucket_size : Int32)
    @bucket = Array(Array(Int32)).new((@n + @bucket_size - 1) // @bucket_size) { [] of Int32 }
    @qs = Array(Tuple(Int32, Int32)).new
  end

  def add_query(l : Int32, r : Int32)
    @bucket[l // @bucket_size] << @qs.size
    @qs << {l, r}
  end

  def build
    @bucket.size.times do |i|
      @bucket[i].sort_by! { |qi| @qs[qi][1] }
      if i % 2 != 0
        @bucket[i].reverse!
      end
    end
  end

  def each
    @bucket.each do |b|
      b.each do |qi|
        yield ({@qs[qi][0], @qs[qi][1], qi})
      end
    end
  end
end

class RBST(T)
  class Node(T)
    @left : Node(T) | Nil
    @right : Node(T) | Nil
    property :left, :right
    getter :val, :size

    def initialize(@val : T)
      @left = nil
      @right = nil
      @size = 1
    end

    def height
      if left = @left
        lh = left.height
      else
        lh = 0
      end
      if right = @right
        rh = right.height
      else
        rh = 0
      end
      return {lh, rh}.max + 1
    end

    def fix_size
      @size = 1
      if left = @left
        @size += left.size
      end
      if right = @right
        @size += right.size
      end
    end

    def to_s(io : IO)
      to_s(io, 0)
    end

    def to_s(io : IO, level : Int32)
      if left = @left
        left.to_s(io, level + 1)
      end
      io << " " * level * 2 << @val << "\n"
      if right = @right
        right.to_s(io, level + 1)
      end
    end
  end

  @root : Node(T) | Nil

  def initialize
    @root = nil
    @rnd = Random.new
  end

  def insert(v : T)
    @root = insert(@root, v)
  end

  def insert(node : Node(T) | Nil, v : T) : Node(T)
    return Node(T).new(v) if !node
    if @rnd.rand(node.size + 1) == 0
      return insert_root(node, v)
    end
    if v < node.val
      node.left = insert(node.left, v)
    else
      node.right = insert(node.right, v)
    end
    node.fix_size
    return node
  end

  def insert_root(node : Node(T) | Nil, v : T) : Node(T)
    return Node(T).new(v) if !node
    if v < node.val
      node.left = insert_root(node.left, v)
      return rotate_right(node)
    else
      node.right = insert_root(node.right, v)
      return rotate_left(node)
    end
  end

  def rotate_right(node : Node(T)) : Node(T)
    top = node.left.not_nil!
    mid = top.right
    top.right = node
    node.left = mid
    node.fix_size
    top.fix_size
    return top
  end

  def rotate_left(node : Node(T)) : Node(T)
    top = node.right.not_nil!
    mid = top.left
    top.left = node
    node.right = mid
    node.fix_size
    top.fix_size
    return top
  end

  def clear
    @root = nil
  end

  def remove(v : T) : Bool
    new_root, found = remove(@root, v)
    if found
      @root = new_root
      return true
    else
      return false
    end
  end

  def remove(node : Node(T) | Nil, v : T) : Tuple(Node(T) | Nil, Bool)
    return {nil, false} if !node
    if v == node.val
      return {meld(node.left, node.right), true}
    elsif v < node.val
      new_child, found = remove(node.left, v)
      if found
        node.left = new_child
        node.fix_size
      end
    else
      new_child, found = remove(node.right, v)
      if found
        node.right = new_child
        node.fix_size
      end
    end
    return {node, found}
  end

  def meld(left : Node(T) | Nil, right : Node(T) | Nil) : Node(T) | Nil
    return right if !left
    return left if !right
    if @rnd.rand(left.size + right.size) < left.size
      left.right = meld(left.right, right)
      left.fix_size
      return left
    else
      right.left = meld(left, right.left)
      right.fix_size
      return right
    end
  end

  def find(v : T) : Node(T) | Nil
    cur = @root
    while cur
      if v == cur.val
        return cur
      elsif v < cur.val
        cur = cur.left
      else
        cur = cur.right
      end
    end
    return nil
  end

  def nth(n : Int32) : T
    # 0-indexed
    cur = @root
    while cur
      ln = cur.left
      lc = ln ? ln.size : 0
      if lc > n
        cur = cur.left
      elsif lc < n
        cur = cur.right
        n -= lc + 1
      else
        break
      end
    end
    if cur
      return cur.val
    else
      raise Exception.new("cannot fine")
    end
  end

  def rank(v : T) : Int32
    # 0-indexed, not count equivalent values
    cur = @root
    ret = 0
    while cur
      if v <= cur.val
        cur = cur.left
      else
        if left = cur.left
          ret += left.size
        end
        ret += 1
        cur = cur.right
      end
    end
    return ret
  end

  def lower(v : T) : T | Nil
    # largest value smaller than v
    cur = @root
    ret = nil
    while cur
      if cur.val < v
        ret = cur.val
        cur = cur.right
      else
        cur = cur.left
      end
    end
    return ret
  end

  def upper(v : T) : T | Nil
    # smallest value larger than v
    cur = @root
    ret = nil
    while cur
      if cur.val > v
        ret = cur.val
        cur = cur.left
      else
        cur = cur.right
      end
    end
    return ret
  end

  def size
    if root = @root
      return root.size
    else
      return 0
    end
  end

  def height
    if root = @root
      root.height
    else
      0
    end
  end

  def to_s(io : IO)
    if root = @root
      root.to_s(io, 0)
    else
      io << "nil\n"
    end
  end
end

class BIT(T)
  # 1-indexed

  def initialize(size : Int)
    len = 1
    while len < size
      len *= 2
    end
    @v = Array(T).new(len + 1, T.zero)
  end

  def cumulative_sum(index : Int)
    ret = T.zero
    while index > 0
      ret += @v[index]
      index &= index - 1
    end
    ret
  end

  def sum(l : Int, r : Int)
    cumulative_sum(r) - cumulative_sum(l - 1)
  end

  def add(index : Int, val : T)
    while index < @v.size
      @v[index] += val
      index += (index & -index)
    end
  end

  def set(index : Int, val : T)
    old = sum(index, index)
    add(index, val - old)
  end
end

n, q = read_line.split.map(&.to_i)
a = read_line.split.map(&.to_i64)
b = read_line.split.map(&.to_i64)
mo = Mo.new(n, 300)
q.times do
  l, d, r, u = read_line.split.map(&.to_i)
  mo.add_query(l - 1, d - 1)
  mo.add_query(r, u)
  mo.add_query(l - 1, u)
  mo.add_query(r, d - 1)
end
mo.build
ans = Array.new(q, 0i64)
row = RBST(Int64).new
col = RBST(Int64).new
sum_row = BIT(Int64).new(100001)
sum_col = BIT(Int64).new(100001)
sum = 0i64
cl = 0
cr = 0
mo.each do |nl, nr, qi|
  # expand
  while cr < nr
    sum += b[cr] * col.rank(b[cr])
    sum += sum_col.sum(b[cr], 100000)
    row.insert(b[cr])
    sum_row.add(b[cr], b[cr])
    cr += 1
  end
  while cl < nl
    sum += a[cl] * row.rank(a[cl])
    sum += sum_row.sum(a[cl], 100000)
    col.insert(a[cl])
    sum_col.add(a[cl], a[cl])
    cl += 1
  end

  # shrink
  while cr > nr
    cr -= 1
    sum -= b[cr] * col.rank(b[cr])
    sum -= sum_col.sum(b[cr], 100000)
    row.remove(b[cr])
    sum_row.add(b[cr], -b[cr])
  end
  while cl > nl
    cl -= 1
    sum -= a[cl] * row.rank(a[cl])
    sum -= sum_row.sum(a[cl], 100000)
    col.remove(a[cl])
    sum_col.add(a[cl], -a[cl])
  end
  ans[qi // 4] += sum * (qi % 4 < 2 ? 1 : -1)
end
puts ans.join("\n")
0