番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*1インデックスを求めること。数列の長さ:要素の値:クエリの数:単に最小値だけが欲しい場合は、RMQ*2を処理するセグメントツリーを実装すれば良い。2を効率良く処理することができる。それには、各ノードに対し「区間の最小値(minとおく)」に加え、「区間中に最小値を達成した最も左端のインデックス(minIndexとおく)」を持つようにする。区間をマージするときは、次のようにする。左右の区間が同じ最小値を持つ場合は、インデックスを左側の区間に合わせる。左右の区間の最小値が異なるときは、インデックスを最小値を持つ方に合わせる。まとめて、左の区間値が右の区間値よりも等しいか小さい場合、値を左側の区間に合わせる、とすると実装が楽になるだろう。Javaによる実装は以下の通り。クエリにも答えてみよう。☆は本問と同程度、★は少し難しい。番目の値の中で、最小値とそのインデックスを求める。