University of Aizu Programming Contest 2012（AOJ 1508）RMQ
お題箱より。
解法
1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存在する要素のインデックスがずれます。そのため、インデックスに基づいて固定された構造を持つセグメント木では対応できません。
ではどうすれば良いのかというと、インデックスに依存しない構造を持つ平衡二分木を用いれば良いです。これなら要素の削除と追加ができます。
ということで、残りはこの問題と言うより平衡二分木の解説になってしまいますが…平衡二分木については非常に有名なスライドがあるのでこれを紹介します。
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～
平衡二分木の話は少し紛らわしくて、解説やサンプルコードなどを読む際には以下の2種類のどちらを目的としたものなのかを意識する必要があります。
- C++の
std::setのような順序付き集合としての機能。要素を順序付きで保持する。値の追加や削除、小さい方から番目の要素の取得、大小関係に基づく二分探索、区間クエリの処理などができる。
- 数列の拡張としての機能。要素を列としての並びに基づいて保持する。
個人的には前者を特に「平衡二分探索木」と呼び、主に後者を指す時に「平衡二分木」という言葉を使うようにしていますが、競プロerの中でも確かな呼び分けがされていないように思います。先ほどのスライドで紹介されているTreapの実装は後者で、この問題で必要なのも後者です。
このスライドの実装に区間クエリの処理機能を追加します。やることはセグメント木と同様で、まず各ノードは自身以下の部分木の値を全てマージした計算済みの値（今回の問題では最小値）を常に持つようにしておきます。この値はスライドの実装の cnt や sum と同様に、自身以下の部分木が変化した時に計算し直せば良いです。
クエリ処理する時には根から再帰的に見ていって、各ノードは親に以下のような値を返すようにします。
- 対象ノード以下の部分木が受け持っているインデックス範囲が、
- クエリ対象範囲と全く重複していないならば、単位元を返す。
- クエリ対象範囲に完全に含まれているならば、計算済みの値を返す。
- そうでないならば、左の子が返した値、（もしノード自身のインデックスが範囲に含まれているならば自身の値、）右の子が返した値をマージした値を返す。
セグメント木とは異なり各ノードが受け持つインデックス範囲が固定されていませんが、部分木のサイズ cnt は分かるので、根から再帰的に呼び出すときに各ノードのオフセット（その部分木より左にいくつ要素があったか）を渡していくことで知ることができます。
