問題解決の宝石箱

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

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

データ構造

f:id:hama_DU:20161015004003p:plain

hama-du-competitive.hatenablog.com

前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。

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

全ての問題において、制約は以下の通り。

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

問題1

  • i 番目の値を v に変更する。
  • l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計 を出力。

問題2

  • i 番目の値を v に変更する。
  • l 番目から r 番目の値の中で、 最も左端で*1 v 以下になるインデックス を求める。存在しない場合はその旨を報告。

問題3

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

解答1

通常の「区間の最小値(minとおく)」を持つRMQセグメントツリーに、「区間内の最小インデックスの和(sumIndexとおく)」を持たせればよい。 区間をマージするときは、子の min が等しいときは　sumIndex を合計、そうでないときは min が小さい方に合わせる。ただし、sumIndex が 32bit整数に収まらないことがあるので注意（露骨な罠）

解答例では、区間に入ってる値たちをクラスに包んで実装してみた*3*4。以下3つを準備しておくと便利だろう

  • 指定の min、sumIndex で生成（コンストラクタ）
  • ダミー値（今回の場合はmin=INF, sumIndex=0）を生成する関数
  • 値をコピーする関数（clone）

解答2

追加の情報を持たせる必要はないが、探索を少し工夫する。区間最小値を求める時と同じノリで、場合分けをしよう。

  • クエリの区間が今見ている区間より外にあるとき => ここには答えがない。適当な大きい数を返そう。
  • クエリの区間の最小値が v より大きいとき => ここには答えがない。適当な大きい数を返そう。

↑2つに当てはまらない、ということは、今自分が最下段にいるか、左右の子に答えがあるかのどちらかなので、

  • 最下段にいる場合 => そのインデックスが答え。
  • 左の子が v 以下である => 左の子に対して再帰関数を呼ぶ。
  • 左の子が v より大きい => 右の子に対して再帰関数を呼ぶ。

とすれば、区間を訪れる数が { O(\log{n} )} に収まる。

解答3

区間更新クエリに対する常套手段として、区間更新を最も広い区間たちで一旦受け止めておいて、区間を触るときに子に伝搬するというテクニックがある。 少し高度な概念になるが、本稿では理屈については扱わず適用方法だけを述べる。*5

「最小値(min)」「最左インデックス(minIndex)」に加え、「遅延評価中の最小値(delayMin)」「遅延評価中の最左インデックス(delayMinIndex)」を持っておく。delayMin および delayMinIndex は「値を持っていない」ことを示す適当な値を入れておく。

「区間更新」「区間参照」どちらも、上から降りていく形で作業が進むが、このとき区間にたどり着くたびに、以下の処理を行う。（実装上例ではpushDown関数）

  • 今の区間の delayMin および delayMinIndex が空の場合、何もしない。
  • delayMin および delayMinIndex を 自身の min minIndex に適用する。
  • 子がいない場合は終了。
  • 値を「子に降ろし」て、delayMin, delayMinIndex を空にする。ただし、delayMinIndex を右の子に下ろすとき、値を変更する必要があるので注意。*6

また、左右の子の再帰関数から戻ってきた後は、以下の処理を行う。（実装例では pullUp関数）

  • 左右の子の値 min minIndex *7 から値を「吸い上げ」て自分の min minIndex を更新する。

解答コード

長いのでリンクのみ示す。(gist)

SegmentTreePractice

*1:最も l に近い

*2:最も l に近い

*3:Javaにも標準でTupleが欲しい・・・

*4:Javaにおける実行速度についてはあんまり検討してないです・・・オブジェクトの生成オーバーヘッドがやばそう

*5:長くなってしまうので・・・

*6:そのため、実装例ではpushDown関数にインデックス値(l,r)を渡している

*7:この時点で、左右の子の min、minIndex は正しい値を持っているはず