問題 marunomi の性質

問題 marunomi について以下の性質がなりたちます。

• スライム i とスライム j の最終的な重さの最大値が異なるならばその重さの比は二倍以上である。
• 最終的な重さの最大値の種類数は \(O(\log (N\max(W)))\) である。

解法

各prefix におけるスライムの勝利数は \(O(\log (N\max(W)))\) 種類しか存在しないため、勝利数が等しくなるようなスライムの最小と最大の重さの組をセットで持ち、更新する事を考えます。

まず、 segment tree / binary indexed tree 等、一点更新・区間和を管理するデータ構造によって、現在の重みより小さいスライムの重さの和を持ちます。

ここで、新しくスライムを一匹追加することを考えます。

すると、新しく追加するスライムの勝利数の計算は \(O(\log N\log(N\max(W)))\) かかり、それぞれの勝利数が等しいスライムに関しても \(O(\log N\log (N\max(W)))\) で同時に更新することができるので、全体で \(O(\log N\log^2 (N\max(W)))\) で計算できます。勝利数が等しいスライムのマージも \(O(\log (N\max(W)))\) でできます。

よって、この問題は \(O(N\log N \log^2(N\max(W)))\) で解くことができました。また、問題の性質をうまく使うことで更新毎の一点更新・区間和を管理するデータ構造へのアクセス回数を減らし、 \(O(N\log N \log(N\max(W)))\) の計算量で解くこともできます。