結果

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

ソースコード

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 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, 140)
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)
cnt_row = BIT(Int32).new(100001)
cnt_col = BIT(Int32).new(100001)
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] * cnt_col.cumulative_sum(b[cr] - 1)
    sum += sum_col.sum(b[cr], 100000)
    cnt_row.add(b[cr], 1)
    sum_row.add(b[cr], b[cr])
    cr += 1
  end
  while cl < nl
    sum += a[cl] * cnt_row.cumulative_sum(a[cl] - 1)
    sum += sum_row.sum(a[cl], 100000)
    cnt_col.add(a[cl], 1)
    sum_col.add(a[cl], a[cl])
    cl += 1
  end

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