noshi91のメモ

データ構造のある風景

ARC098 E Range Minimum Queries O(NlogN)解法

はじめに

 ARC098お疲れさまでした。Fを終了1分前に記念提出したらサンプル以外ACしていた(=埋め込みで全完狙えてた)ので少し残念な気持ちです。それはそうとE問題が準線形時間で解けることが解説で示唆されていたのでそれについて書こうと思います。E問題の完全なネタバレを含むため注意してください。

 

 

=====================================ネタバレ注意=======================================

 

 

 

方針

 最小値を決め打ちしますが、大きい値から順番に試していくことにします。選べる値をヒープでQ個確保しておいて、新たに選べる値が増えたら "ヒープに入れる→最大値を削除" を行えば常に小さい方からQ個を保持できます。ここで使用するヒープをヒープHと呼ぶことにします。

 問題は最小値を変化させたときの選べる値の変化です。ここで、選べる値は連続する部分列毎に独立に管理できることに着目します。「使用できる列のうち大きい方から(K-1)個のみが使用不可能」という性質から、meldable heap の出番であることが分かります。列ごとに大きいほうから(K-1)個をヒープで保持しておき、2つの列が合わさるときには "ヒープをマージ→ヒープの要素が(K-1)個になるまで小さいほうからヒープHに入れて削除" を行えばよいです。

 

計算量

 ヒープHには全ての値が高々1回づつしか挿入/削除されないので O(NlogN)

 ヒープのマージがO(logN)、マージは高々N回なので O(NlogN)

 マージ後の削除は2行上と同じ解析で高々N回なので O(NlogN)

 よって全体で O(NlogN) で解けます。C++STLだけでも O(Nlog^2N) は簡単に達成できるので、マイナーなデータ構造は必須ではありません。

 

実装

 meldable heap を持っていれば簡単です。

arc098.contest.atcoder.jp

 丁度 interval heap と永続leftist heap を実装していたので使用してみました。meldable heap を使う時は Union Find Tree の併合操作で元の2つの根を返すようにすると便利です。