セグメント木を用いるとシミュレーションができます。

まず座標圧縮を行います。

双対セグ木の要領で、各区間を含む仲良しグループを列挙しておきます。これらの数の総和は \(O(N \log N)\) です。

次のような遅延セグ木を考えます。

• (幸福度, index), (終了状態) の2 状態を持つ。
• 区間積は問題の取る順に従う、ただし終了状態はもっとも後回し。
• 区間を \(x\) で更新するとき、終了状態以外の幸福度を \(\max\) で置き換える。

これは実際にモノイドになっています。

あとは \(O(N)\) 回全体取得をし、そのステップで招待する動物が決まったら前述の双対セグ木を用いてその動物を含む仲良しグループを列挙し更新すればよいだけです。

計算量は \(O(N \log N)\) です。

提出 (https://atcoder.jp/contests/joisc2012/submissions/35967813)