問題解決の宝石箱

競技プログラミング／数学ネタ置き場

指定区間の最大値／最小値のインデックスを求めるクエリにたくさん答えたい part1

典型 データ構造 ☆4

この問題を以下のように定式化した。効率よく解けるだろうか？

長さ {N} の数列 { a_{1}, a_{2}, ... , a_{N} } が与えられる。以下のクエリに {Q} 個答えよ。

  • クエリ1 : i 番目の値を v に変更する。
  • クエリ2 : l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*1インデックスを求めること。

制約は以下の通り。

  • 数列の長さ：{ 1 \leq N \leq 10^5 }
  • 要素の値：{ 1 \leq a_{i}, v \leq 10^9 }
  • クエリの数：{ 1 \leq Q \leq 10^5 }

単に最小値だけが欲しい場合は、RMQ*2を処理するセグメントツリーを実装すれば良い。詳細については、「プログラミングコンテストチャレンジブック 」*3 もしくは Goで型を挿げ替え可能なデータ構造ライブラリを作る - Qiita *4 を参照のこと。

この通常のセグメントツリーに少し手を加えることで、クエリ1, および2を効率良く処理することができる。 それには、各ノードに対し「区間の最小値(minとおく)」に加え、「区間中に最小値を達成した最も左端のインデックス(minIndexとおく)」を持つようにする。

f:id:hama_DU:20161010234212p:plain

区間をマージするときは、次のようにする。

  • 左右の区間が同じ最小値を持つ場合は、インデックスを左側の区間に合わせる。
  • 左右の区間の最小値が異なるときは、インデックスを最小値を持つ方に合わせる。

まとめて、左の区間値が右の区間値よりも等しいか小さい場合、値を左側の区間に合わせる、とすると実装が楽になるだろう。Javaによる実装は以下の通り。

public int[] merge(int leftMin, int leftIdx, int rightMin, int rightIdx) {
    if (leftMin <= rightMin) {
        return new int[]{leftMin, leftIdx};
    } else {
        return new int[]{rightMin, rightIdx};
    }
}

実装例

練習問題

以下のクエリにも答えてみよう。☆は本問と同程度、★は少し難しい。

  • クエリ3☆ : l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計 を出力。
  • クエリ4☆ : l 番目から r 番目の値の中で、 最も左端で*5 v 以下になるインデックス を求める。存在しない場合はその旨を報告。
  • クエリ5★ : l 番目から r 番目の値を v に変更する。その上で、クエリ2 に正しく答えること。

*1:最も l に近い

*2:Range Minimum/Maximum Query

*3:通称『蟻本』

*4:Go言語が分からなくても、一般的な話をしてる部分だけ読めば大丈夫

*5:最も l に近い