ABC137 D - Summer Vacation - 高温処理済みコースケ

解説(別解のマトロイドのほう)を読みながら、UnionFind木の構造を少し変えると、うまく解けそうとおもったら解けたので記念に貼っておく。

解説では以下のようにセグメント木を使う説明だったけど、セグメント木とかつかわず、もうすこし簡単にやりたいとおもって考えていた。

すなわち、上の手順 2 は、M 日後から x 日前よりも以前であって、まだどの日雇いアルバイトも割り当て
られていない日のうち最も遅い日が高速に求まれば高速に判定できます。これは、区間の最大値を求められ、
一点更新が可能なセグメント木を使えば、S に対する割り当ての情報を保持しながら y に対して O(logM)
で判定できるため、ソートも合わせて全体として O(NlogN + NlogM) で解くことができます。

APIとしてはJavaのBitset#nextClearBitが高速ならよいのだよなとおもって考えていたら、UnionFind木の要領でビットが連続して立っている区間の終端を管理/更新しておけばよいのだよなと気づいた。
UnionFInd木でunion(a,b)するのをunion(a,a+1)に限定するイメージでできたコードがこれ。

N, M = gets.split.map(&:to_i)
S = N.times.map { gets.split.map(&:to_i) }.sort_by{|v| -v[1] }
bitset = Array.new(M + 1, &:itself) # a variant of Union Find Tree.

class << bitset
  def next_clear_bit(base)
    return size if base >= size
    return base if self[base] == base
    self[base] = next_clear_bit(self[base])
  end
  
  def extend_trailing_set_bits(base)
    r = next_clear_bit(base)
    return nil if r >= size
    self[r] = next_clear_bit(r + 1)
    r
  end
end

puts S.inject(0){|s, (a, b)| 
  bitset.extend_trailing_set_bits(a) ? s + b : s 
}

これでたぶん計算量としては N log N + N α(M) になる。(αはアッカーマン関数)

このデータ構造は実装も簡単だし、重複のない区間を併合するみたいな感じっぽいので、もしかしたら使いどころが結構あるかもしれないとおもった。

また2部グラフの最小(最大)コストマッチングが下記条件を満たす場合はこのアルゴリズムでできるってことだと思うのでメモ

2部グラフ $G \left( U \cup V, E \right)$ は頂点集合U（今回はアルバイト) , V(今回は日付)と辺集合E (マッチング候補)からなる
Uは重みによりソート可能
Vは $\{ 1 \dots |V| \}$ に対して、全単射でUから見たマッチングの優先度もこれに従う
Uの任意の点uを終端とする辺の集合 $E_u \subset E$ が、 $\exists d \in \mathbb{N}$ に割り当て可能(今回はuの報酬の受取日でVをマッチング可能、不可能に分割できる)

atcoder.jp