2012JOI春合宿1-2 Fish 解説

解説

長さを区間 $[x,2x)$ で区切ると、この中にある魚の部分集合は自由に選んで飼える。逆に、全部の魚の部分集合のうち飼うことのできるものを適当に選ぶと必ずこのような $x$ をとれる。

区間の種類数は高々 $O(N)$ で、尺取り法を使えば $O(N)$ で列挙できる。

ある区間について、赤・緑・青の魚の数をそれぞれ $R,G,B$ とすれば、$r\leq R, g\leq G, b\leq B$ を満たす任意の $r,g,b$ について、赤色 $r$ 匹・緑色 $g$ 匹・青色 $b$ 匹という飼い方ができる。

3色の魚の数を3次元の直交座標に対応づければ、問題は次のように言い換えられる。

$R\times G\times B$ の直方体が $N$ 個与えられる。これらの直方体の和集合の体積はいくらか？

どれかの辺を降順にソートして考えると、順に上から足していけばユークリッド平面上で長方形の和集合の面積を求める問題に帰着できる。ここで、行いたい操作は長方形の追加と総面積の計算だが、長方形のひとつの頂点は必ず原点にあるので、区間更新総和取得ができるセグメントツリーで計算することができる。

ただし、図形に $(i,y)$ が含まれない最小の $i$ を求めるクエリも必要となるので、区間 max のセグメントツリーも作って二分探索をすれば計算量 $O(N\log N)$ でこの問題が解ける。