ABC 401-500/ABC440F - Egoism - 競技プログラミング用 知識集積所

---

問題

ABC440F

必要知識

B以下レベルの内容は省略

• 特になし

考え方

基本的には、丁寧さ2の馬がk頭いる場合、機嫌が高い方からk頭をその後ろにすればいい。
ただし、

• 全員丁寧さ2の場合、最下位のやつは諦める
• 機嫌が高い方からk頭（全員ではない）が丁寧さ2の馬と同じメンバーだった場合は、k位のやつは諦めて、k+1位のやつを採用する

という特殊なケースへの対応が必要となる。

よって、2つのset※を用意して、それぞれにk位までとk+1位からの馬の一覧を用意すればよい。
このとき、常に

• それぞれの機嫌の合計
• それぞれに丁寧さ2の馬が何頭いるか

も同時に管理する。

クエリが来た時には、

• 元のデータを取り除く
• 新しいデータをk+1位以下側に追加する
• k位以上側の下位2つ（存在すれば）をk+1位以下側に戻す
  • 丁寧さ2ｎ馬が1頭減る可能性と、下位の馬が上位に移動する可能性で、最大2頭まで下位落ちする可能性がある
• 上位がk頭になるまで下位のトップを上位側に移す

という方法で処理できる。

解答は、

• 基本的に、上位の合計*2+下位の合計が答え
• 下位に丁寧さ2のやつがいない場合、上位の中の最下位分を引く（1倍相当にする）
• 下位に丁寧さ2のやつがいないが1のやつはいる場合、さらに下位の中の最上位を足す（2倍相当にする）

で求められる。

解答例

解答例

注意点

long long型が必要。

答えはint型を大きく超えることがある。
long long型を適切に用いること。

別解